{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximize the Minimum Powered City"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #queue #array #binary-search #prefix-sum #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #队列 #数组 #二分查找 #前缀和 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxPower"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最大化城市的最小电量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始长度为 <code>n</code>&nbsp;的整数数组&nbsp;<code>stations</code>&nbsp;，其中&nbsp;<code>stations[i]</code>&nbsp;表示第 <code>i</code>&nbsp;座城市的供电站数目。</p>\n",
    "\n",
    "<p>每个供电站可以在一定 <strong>范围</strong>&nbsp;内给所有城市提供电力。换句话说，如果给定的范围是&nbsp;<code>r</code>&nbsp;，在城市&nbsp;<code>i</code>&nbsp;处的供电站可以给所有满足&nbsp;<code>|i - j| &lt;= r</code> 且&nbsp;<code>0 &lt;= i, j &lt;= n - 1</code>&nbsp;的城市&nbsp;<code>j</code>&nbsp;供电。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>|x|</code>&nbsp;表示 <code>x</code>&nbsp;的 <strong>绝对值</strong>&nbsp;。比方说，<code>|7 - 5| = 2</code>&nbsp;，<code>|3 - 10| = 7</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>一座城市的 <strong>电量</strong>&nbsp;是所有能给它供电的供电站数目。</p>\n",
    "\n",
    "<p>政府批准了可以额外建造 <code>k</code>&nbsp;座供电站，你需要决定这些供电站分别应该建在哪里，这些供电站与已经存在的供电站有相同的供电范围。</p>\n",
    "\n",
    "<p>给你两个整数&nbsp;<code>r</code> 和&nbsp;<code>k</code>&nbsp;，如果以最优策略建造额外的发电站，返回所有城市中，最小电量的最大值是多少。</p>\n",
    "\n",
    "<p>这 <code>k</code>&nbsp;座供电站可以建在多个城市。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>stations = [1,2,4,5,0], r = 1, k = 2\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>\n",
    "最优方案之一是把 2 座供电站都建在城市 1 。\n",
    "每座城市的供电站数目分别为 [1,4,4,5,0] 。\n",
    "- 城市 0 的供电站数目为 1 + 4 = 5 。\n",
    "- 城市 1 的供电站数目为 1 + 4 + 4 = 9 。\n",
    "- 城市 2 的供电站数目为 4 + 4 + 5 = 13 。\n",
    "- 城市 3 的供电站数目为 5 + 4 = 9 。\n",
    "- 城市 4 的供电站数目为 5 + 0 = 5 。\n",
    "供电站数目最少是 5 。\n",
    "无法得到更优解，所以我们返回 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>stations = [4,4,4,4], r = 0, k = 3\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>\n",
    "无论如何安排，总有一座城市的供电站数目是 4 ，所以最优解是 4 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == stations.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= stations[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= r&nbsp;&lt;= n - 1</code></li>\n",
    "\t<li><code>0 &lt;= k&nbsp;&lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximize-the-minimum-powered-city](https://leetcode.cn/problems/maximize-the-minimum-powered-city/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximize-the-minimum-powered-city](https://leetcode.cn/problems/maximize-the-minimum-powered-city/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,4,5,0]\\n1\\n2', '[4,4,4,4]\\n0\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        d = [0] * (n+1)\n",
    "        \n",
    "        for i in range(n):\n",
    "            left, right = max(0, i-r), min(n-1, i+r)\n",
    "            d[left] += stations[i]\n",
    "            d[right+1] -= stations[i]\n",
    "            #d[i] += stations[i] \n",
    "\n",
    "        def check(x, kk):\n",
    "            dd = copy.deepcopy(d)\n",
    "            tot = 0\n",
    "            for i in range(n):\n",
    "                tot += dd[i] \n",
    "                if tot < x:\n",
    "                    kk -= x - tot \n",
    "                    dd[i] += x - tot\n",
    "                    if i + 2 * r +1 <= n:\n",
    "                        dd[i+2*r+1] -= x - tot \n",
    "                    tot = x \n",
    "            return kk >= 0\n",
    "        \n",
    "\n",
    "        mn,mx = 0, sum(stations) + k\n",
    "        while mn < mx:\n",
    "            mid = (mn + mx + 1) >> 1\n",
    "            if check(mid, k):\n",
    "                mn = mid \n",
    "            else:\n",
    "                mx = mid - 1\n",
    "        return mx\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        dif = [0]*(n+1)\n",
    "        for i,num in enumerate(stations):\n",
    "            left = max(i-r,0)\n",
    "            right = min(i+r,n-1)\n",
    "            dif[left]+=num\n",
    "            dif[right+1]-=num\n",
    "        def check(x):\n",
    "            d = dif[:]\n",
    "            need = cur = 0\n",
    "            for i in range(n):\n",
    "                cur += d[i]\n",
    "                if cur<x:\n",
    "                    need += x-cur\n",
    "                    d[i] += x-cur\n",
    "                    d[min(i+2*r,n-1)+1] -= x-cur\n",
    "                    cur = x\n",
    "            return need <=k\n",
    "                    \n",
    "        left = 0\n",
    "        right = 10**11\n",
    "        while left<=right:\n",
    "            mid = (left+right)>>1\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid-1\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        diff = [0] * (n + 1)\n",
    "        for i, v in enumerate(stations):\n",
    "            diff[max(0, i - r)] += v\n",
    "            diff[min(n, i + r + 1)] -= v\n",
    "\n",
    "        def check(mn_v):\n",
    "            sm, cnt = 0, 0\n",
    "            dd = diff[:]\n",
    "            for i in range(n):\n",
    "                sm += dd[i]\n",
    "                if sm < mn_v:\n",
    "                    cnt += mn_v - sm\n",
    "                    dd[i] += mn_v - sm\n",
    "                    dd[min(n, i + r * 2 + 1)] -= mn_v - sm\n",
    "                    if cnt > k: return False\n",
    "                    sm = mn_v\n",
    "            return True\n",
    "\n",
    "        lp, rp = 0, 10**11\n",
    "        ans = 0\n",
    "        while lp <= rp:\n",
    "            mid = lp + (rp - lp) // 2\n",
    "            if check(mid):\n",
    "                ans = mid\n",
    "                lp = mid + 1\n",
    "            else:\n",
    "                rp = mid - 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        df = [0] * (n + 5)\n",
    "        for i, j in enumerate(stations):\n",
    "            df[max(0, i - r)] += j\n",
    "            df[min(n - 1, i + r) + 1] -= j\n",
    "        lo, hi = min(accumulate(df[:n])), 2 * 10 ** 10\n",
    "        def check(mid):\n",
    "            diff = df[:]\n",
    "            cur, cnt = 0, 0\n",
    "            for i in range(n):\n",
    "                cur += diff[i]\n",
    "                if cur < mid:\n",
    "                    cnt += mid - cur\n",
    "                    diff[min(n - 1, i + 2 * r) + 1] -= mid - cur\n",
    "                    cur = mid\n",
    "                if cnt > k: return False\n",
    "            return True\n",
    "    \n",
    "        while lo < hi:\n",
    "            mid = lo + hi + 1 >> 1\n",
    "            if check(mid): lo = mid\n",
    "            else: hi = mid - 1\n",
    "        return lo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        \n",
    "        diff = [sum(stations[:r+1])]\n",
    "        for i in range(1, len(stations)):\n",
    "            c = 0\n",
    "            rmv = i - r - 1\n",
    "            pls = i + r\n",
    "            if rmv >= 0: c -= stations[rmv]\n",
    "            if pls < len(stations): c += stations[pls]\n",
    "            diff.append(c)\n",
    "            \n",
    "        def calc(x):\n",
    "            c = 0\n",
    "            nk = k\n",
    "            cdiff = diff[:]\n",
    "            for i in range(len(stations)):\n",
    "                c += cdiff[i]\n",
    "                if c < x:\n",
    "                    if nk < x - c: return False\n",
    "                    nk -= x - c\n",
    "                    idx = min(len(stations)-1, i+r) + r + 1\n",
    "                    if idx < len(stations): cdiff[idx] -= x - c\n",
    "                    c = x\n",
    "            return True\n",
    "        \n",
    "        left, right = 0, k + sum(stations)\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if calc(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def check(self, target, counts, r, k):\n",
    "        temp_k = k\n",
    "        temp =[]\n",
    "\n",
    "\n",
    "        s = [0] * len(counts)\n",
    "        pre = 0\n",
    "        for i in range(len(counts)):\n",
    "            if i - r > 0 :\n",
    "                pre -= s[i - r - 1]\n",
    "            dis = counts[i] + pre - target\n",
    "            if dis < 0:\n",
    "                temp_k += dis\n",
    "                if temp_k < 0:\n",
    "                    return False\n",
    "                place = min(len(counts) - 1, i + r)\n",
    "                s[place] = -dis\n",
    "                pre += s[place]\n",
    "            temp.append(pre)\n",
    "\n",
    "        return temp_k >= 0\n",
    "\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        counts = []\n",
    "        pre = 0\n",
    "        for i in range(r):\n",
    "            pre += stations[i]\n",
    "        for i in range(len(stations)):\n",
    "            if i + r < len(stations):\n",
    "                pre += stations[i + r]\n",
    "            if i - r >0 :\n",
    "                pre -= stations[i - r-1]\n",
    "            counts.append(pre)\n",
    "\n",
    "        left = 0\n",
    "        right = 1e11\n",
    "        while right - left > 4:\n",
    "            target = int((left + right) // 2)\n",
    "            if self.check(target, counts, r, k):\n",
    "                left = target\n",
    "            else:\n",
    "                right = target\n",
    "        ans = left\n",
    "        print(f\"{left} {right}\")\n",
    "        left = int(left)\n",
    "        right = int(right)\n",
    "        for i in range(left, right + 1):\n",
    "            if self.check(i, counts, r, k):\n",
    "                ans = i\n",
    "        return ans\n",
    "\n",
    "# Solution().maxPower([4,4,4,4],0,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "\n",
    "        n = len(stations)\n",
    "        sum = list(accumulate(stations, initial=0))  # 前缀和\n",
    "        for i in range(n):\n",
    "            stations[i] = sum[min(i + r + 1, n)] - sum[max(i - r, 0)]  # 电量\n",
    "        print(stations)\n",
    "\n",
    "        def check(min_power: int) -> bool:\n",
    "            diff = [0] * n  # 差分数组\n",
    "            sum_d = need = 0\n",
    "            for i, power in enumerate(stations):\n",
    "                sum_d += diff[i]  # 累加差分值\n",
    "                m = min_power - power - sum_d\n",
    "                if m > 0:  # 需要 m 个供电站\n",
    "                    need += m\n",
    "                    if need > k: \n",
    "                        return True  # 提前退出这样快一些\n",
    "                    sum_d += m  # 差分更新\n",
    "                    if i + r * 2 + 1 < n:\n",
    "                        diff[i + r * 2 + 1] -= m  # 差分更新\n",
    "            \n",
    "            return False\n",
    "\n",
    "\n",
    "      #  print([check(i) for i in range(10)])\n",
    "        return bisect_right(range(max(stations)+k+1),0,key = check)-1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        l = stations[:r + 1]\n",
    "        s = sum(l)\n",
    "        nums = [s]\n",
    "        n = len(stations)\n",
    "        for i in range(1, n):\n",
    "            if i + r < n:\n",
    "                s += stations[i + r]\n",
    "            if i > r:\n",
    "                s -= stations[i - r - 1]\n",
    "            nums.append(s)\n",
    "        left, right = 0, max(nums) + k\n",
    "        # print(nums)\n",
    "        def check(mid):\n",
    "            cnt = 0\n",
    "            o = 0\n",
    "            chafen = [0] * (n + 1 + r + r)\n",
    "            for i in range(n):\n",
    "                o += chafen[i]\n",
    "                if o + nums[i] < mid:\n",
    "                    diff = mid - (nums[i] + o)\n",
    "                    if i < r:\n",
    "                        \n",
    "                        chafen[2 * r + 1] -= diff\n",
    "                        o += diff\n",
    "                    else:\n",
    "                        chafen[i + 2 * r + 1] -= diff\n",
    "\n",
    "                        o += diff\n",
    "                    cnt += diff\n",
    "            return cnt <= k\n",
    "        # print(check(7))\n",
    "        while left < right:\n",
    "            mid = left + right + 1 >> 1\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        length = len(stations)\n",
    "        pre_s = sum(stations[:r]) if r != 0 else 0\n",
    "\n",
    "        def is_min_v_ok(min_val):\n",
    "            sums = stations[:]\n",
    "            lidx = 0\n",
    "            left_k = k\n",
    "            all_sum = pre_s\n",
    "\n",
    "            for i in range(length):\n",
    "                # print(\"sums =\", sums, \"i\", i)\n",
    "                if i + r < length:\n",
    "                    all_sum += sums[i+r]\n",
    "                if i - r - 1 >= 0:\n",
    "                    all_sum -= sums[i-r-1]\n",
    "\n",
    "                if all_sum < min_val:\n",
    "                    cz = min_val - all_sum\n",
    "                    if left_k < cz:\n",
    "                        return False\n",
    "                    left_k -= cz\n",
    "                    sums[min(length - 1, i + r)] += cz\n",
    "                    all_sum += cz\n",
    "            return True\n",
    "        \n",
    "        l, ri = min(stations), sum(stations) + k + 1\n",
    "\n",
    "        while l < ri:\n",
    "            m = (l + ri) // 2\n",
    "            if is_min_v_ok(m):\n",
    "                # print(m, \"ok\")\n",
    "                l = m + 1\n",
    "            else:\n",
    "                # print(m, \"not ok\")\n",
    "                ri = m - 1\n",
    "        # print(\"l\", l)\n",
    "        if is_min_v_ok(l):\n",
    "            return l\n",
    "        return l - 1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        length = len(stations)\n",
    "        pre_s = sum(stations[:r]) if r != 0 else 0\n",
    "\n",
    "        def is_min_v_ok(min_val):\n",
    "            sums = stations[:]\n",
    "            lidx = 0\n",
    "            left_k = k\n",
    "            all_sum = pre_s\n",
    "\n",
    "            for i in range(length):\n",
    "                # print(\"sums =\", sums, \"i\", i)\n",
    "                if i + r < length:\n",
    "                    all_sum += sums[i+r]\n",
    "                if i - r - 1 >= 0:\n",
    "                    all_sum -= sums[i-r-1]\n",
    "\n",
    "                if all_sum < min_val:\n",
    "                    cz = min_val - all_sum\n",
    "                    if left_k < cz:\n",
    "                        return False\n",
    "                    left_k -= cz\n",
    "                    sums[min(length - 1, i + r)] += cz\n",
    "                    all_sum += cz\n",
    "            return True\n",
    "        \n",
    "        l, ri = min(stations), sum(stations) + k + 1\n",
    "\n",
    "        while l <= ri:\n",
    "            m = (l + ri) // 2\n",
    "            if is_min_v_ok(m):\n",
    "                # print(m, \"ok\")\n",
    "                l = m + 1\n",
    "            else:\n",
    "                # print(m, \"not ok\")\n",
    "                ri = m - 1\n",
    "        print(\"l\", l, ri)\n",
    "\n",
    "        return l-1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        D = [0] * (n+1)\n",
    "        for i,x in enumerate(stations): \n",
    "            D[max(0,i-r)] += x \n",
    "            D[min(n,i+r+1) ] -= x \n",
    "        print(D)\n",
    "        def check(y): \n",
    "            D_ = D[:]\n",
    "            use = 0 \n",
    "            s = 0 \n",
    "            for i in range(n):\n",
    "                s += D_[i] \n",
    "                if s < y:\n",
    "                    use += y - s \n",
    "                    D_[min(n,i+2*r+1)] -= y-s \n",
    "                    s = y \n",
    "                    if use > k : \n",
    "                        return 1\n",
    "            return 0 \n",
    "        return bisect_left(range(k+1+sum(stations)),1,key = check) - 1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, a: List[int], p: int, k: int) -> int:\n",
    "        l,r=0,10**18\n",
    "        n=len(a)\n",
    "        def check(m,k):\n",
    "            b=[i for i in a]\n",
    "            c=sum(b[:p])\n",
    "            for i in range(n):\n",
    "                if i-p-1>=0:\n",
    "                    c-=b[i-p-1]\n",
    "                if i+p<n:\n",
    "                    c+=b[i+p]\n",
    "                if c<m:\n",
    "                    if m-c>k:\n",
    "                        return False\n",
    "                    b[min(n-1,i+p)]+=m-c\n",
    "                    k-=m-c\n",
    "                    c+=m-c\n",
    "                # print(b,i,m,k,c)\n",
    "            return True\n",
    "        while l<r:\n",
    "            m=(l+r+1)//2\n",
    "            if check(m,k):\n",
    "                l=m\n",
    "            else:\n",
    "                r=m-1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        def check(n: int)->bool:\n",
    "            used, current = 0, 0\n",
    "            addtions = [0] * (N + R)\n",
    "            for i in range(N):\n",
    "                current += addtions[i] + difference[i]\n",
    "                if current < n:\n",
    "                    gap = n - current\n",
    "                    used += gap\n",
    "                    current += gap\n",
    "                    addtions[i + R] -= gap\n",
    "                if used > k:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        N = len(stations)\n",
    "        R = r + r + 1\n",
    "        difference = [0] * N\n",
    "        for i,station in enumerate(stations):\n",
    "            difference[max(0, i - r)] += station\n",
    "            if i + r + 1< N:\n",
    "                difference[i + r + 1] -= station\n",
    "\n",
    "        low, high = 0, sum(stations) + k\n",
    "        while low < high:\n",
    "            mid = (low + high + 1) // 2\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid - 1\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], R: int, K: int) -> int:\n",
    "        n = len(stations)\n",
    "\n",
    "        def check(LIM: int) -> bool:\n",
    "            vec = []\n",
    "            for p in stations: vec.append(p)\n",
    "\n",
    "            # 初始化滑动窗口的和\n",
    "            sm = 0\n",
    "            for i in range(min(R + 1, n)): sm += vec[i]\n",
    "\n",
    "            # 表示还有几个供电站可以新建\n",
    "            rem = K\n",
    "            # 从左到右计算每个电站的电量，同时维护滑动窗口[l, r]\n",
    "            i, l, r = 0, 0, R\n",
    "            while True:\n",
    "                if sm < LIM:\n",
    "                    # 当前城市电量不足\n",
    "                    delta = LIM - sm\n",
    "                    # 新供电站不够，返回False\n",
    "                    if delta > rem: return False\n",
    "                    # 新供电站足够，建在滑动窗口最右边\n",
    "                    rem -= delta\n",
    "                    vec[r] += delta\n",
    "                    sm += delta\n",
    "                if i == n - 1: break\n",
    "\n",
    "                # 滑动窗口向前移动一个城市\n",
    "                if i >= R:\n",
    "                    sm -= vec[l]\n",
    "                    l += 1\n",
    "                if r != n - 1:\n",
    "                    sm += vec[r + 1]\n",
    "                    r += 1\n",
    "                i += 1\n",
    "            return True\n",
    "\n",
    "        low, high = 0, int(2e10)\n",
    "        while low + 1 != high:\n",
    "            mid = (low + high) >> 1\n",
    "            if check(mid):\n",
    "                low = mid\n",
    "            else:\n",
    "                high = mid\n",
    "        return low"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        i = j = tmp = 0\n",
    "        n = len(stations)\n",
    "        s = [0] * n\n",
    "        while j <= r:\n",
    "            tmp += stations[j]\n",
    "            j += 1\n",
    "        # print(j, tmp)\n",
    "        for p in range(n):\n",
    "            s[p] = tmp\n",
    "            if j != n:\n",
    "                tmp += stations[j]\n",
    "                j += 1\n",
    "            if p - r >= 0:\n",
    "                tmp -= stations[i]\n",
    "                i += 1\n",
    "        # print(s)\n",
    "\n",
    "        def check(min_power):\n",
    "            diff = [0] * n\n",
    "            sum_d = need = 0\n",
    "            for i, power in enumerate(s):\n",
    "                sum_d += diff[i]\n",
    "                delta = min_power - power - sum_d\n",
    "                if delta > 0:\n",
    "                    need += delta\n",
    "                    if need > k:\n",
    "                        return False\n",
    "                    sum_d += delta\n",
    "                    if i + 2*r + 1 < n:\n",
    "                        diff[i + 2*r + 1] -= delta\n",
    "            return True\n",
    "\n",
    "        # 开区间写法\n",
    "        left, right = -1, max(s) + k + 1\n",
    "        while left + 1 < right:  # 左边是True 右边是False\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid) == True:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        s = [0] * (n + 1)\n",
    "        for i in range(1, n + 1): s[i] = s[i - 1] + stations[i - 1]\n",
    "\n",
    "        # mid: 最小化 供电站数目\n",
    "        def check(mid: int) -> bool:\n",
    "            diff = [0] * (n + 1) # 差分数组: 记录该位置需要补充的能量\n",
    "            res, c = 0, 0\n",
    "            for i in range(n):\n",
    "                c += diff[i];\n",
    "                power = s[min(n, i + r + 1)] - s[max(0, i - r)]; # 当前位置的起始能量\n",
    "                m = mid - power - c; \n",
    "                if m > 0: # 需要m个供电站\n",
    "                    res += m;\n",
    "                    if res > k: return False; \n",
    "                    c += m;\n",
    "                    diff[min(i + r * 2 + 1, n)] -= m;\n",
    "            return True;\n",
    "\n",
    "        L, R = 0, sum(stations) + k;\n",
    "        while L < R:\n",
    "            mid = (L + R + 1) // 2;\n",
    "            if check(mid): L = mid;\n",
    "            else: R = mid - 1;\n",
    "        return R"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        nums = [0]*(n)\n",
    "        nums[0] = sum(stations[0:r+1])\n",
    "        for i in range(0, n-1):\n",
    "            nums[i + 1] = nums[i]\n",
    "            if i-r>=0:\n",
    "                nums[i+1] -= stations[i-r]\n",
    "            if i+1+r<n:\n",
    "                nums[i + 1] += stations[i+1+r]\n",
    "        def isValid(res:int) ->bool:\n",
    "            total = extra = 0\n",
    "            cf = [0]*n\n",
    "            for idx,num in enumerate(nums):\n",
    "                extra += cf[idx]\n",
    "                use = res - num - extra\n",
    "                if use>0:\n",
    "                    total += use\n",
    "                    if total>k:\n",
    "                        return False\n",
    "                    extra += use\n",
    "                    if idx+2*r+1<n:\n",
    "                        cf[idx+2*r+1] -= use\n",
    "            return True\n",
    "        left, right = 0, sum(stations)+k+1\n",
    "        while left<right:\n",
    "            mid = (left+right)>>1\n",
    "            if isValid(mid):\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid\n",
    "        return right-1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        s = [0] * (n)\n",
    "        initial = sum(stations[:r+1])\n",
    "        for i,x in enumerate(stations):\n",
    "            s[i] = initial\n",
    "            if i+r+1 <= n-1:\n",
    "                initial += stations[i+r+1]\n",
    "            if i-r >= 0:\n",
    "                initial -= stations[i-r]\n",
    "        left = min(s)\n",
    "        right = left + k\n",
    "        ans = 0\n",
    "        while left < right:\n",
    "            m = (left+right+1) // 2  # 如果我们能够将一个 供电站数目超过 m  即 m+1 那么可以直接进入下一次的 二分\n",
    "            sum_d = [0] * (n+1)\n",
    "            ans = res = 0\n",
    "            # print(\"m:\", left, right, m)\n",
    "            for i,x in enumerate(s):\n",
    "                x += res\n",
    "                if x < m:  # 补上\n",
    "                    sum_d[i] += m-x\n",
    "                    ans += m-x\n",
    "                    if i+2*r+1 <= n:\n",
    "                        sum_d[i+2*r] -= m-x\n",
    "                res += sum_d[i]\n",
    "                if ans > k:\n",
    "                    right = m-1\n",
    "                    break\n",
    "            # print(ans, k, left, right)\n",
    "            if ans <= k:\n",
    "                left = m\n",
    "            # else: right = m-1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        diff = [0]*n\n",
    "        for i in range(n):\n",
    "            left,right = max(0,i-r), min(n-1,i+r)\n",
    "            diff[left] += stations[i]\n",
    "            if right<n-1:\n",
    "                diff[right+1] -= stations[i]\n",
    "            pass\n",
    "\n",
    "        def check(m):\n",
    "            nonlocal r,k\n",
    "            used = 0\n",
    "            cur_diff = diff[:]\n",
    "            presum = 0\n",
    "            for i in range(n):\n",
    "                presum += cur_diff[i]\n",
    "                if presum<m:\n",
    "                    right = min(i+2*r, n-1)\n",
    "                    if right<n-1:\n",
    "                        cur_diff[right+1] -= (m - presum)\n",
    "                    used += (m-presum)\n",
    "                    presum = m\n",
    "            return used<=k\n",
    "\n",
    "        low,high = min(stations),sum(stations)+k+1\n",
    "        res = -1\n",
    "        while low<=high:\n",
    "            mid = (low+high)//2\n",
    "            if check(mid):\n",
    "                res = mid\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid - 1\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        f = [0] * n\n",
    "        for i in range(n):\n",
    "            f[max(0, i-r)] += stations[i]\n",
    "            if i+r+1 <= n-1:\n",
    "                f[i+r+1] -= stations[i]\n",
    "        for i in range(n-1):\n",
    "            f[i+1] += f[i]\n",
    "\n",
    "        def helper(a):\n",
    "            q = deque()\n",
    "            add, res = 0, 0\n",
    "            for i in range(n):\n",
    "                while q and i-2*r > q[0][0]:\n",
    "                    add -= q[0][1]\n",
    "                    q.popleft()\n",
    "                if f[i] + add < a:\n",
    "                    s = a-add-f[i]\n",
    "                    add += s\n",
    "                    res += s\n",
    "                    q.append([i, s])\n",
    "            return res > k\n",
    "\n",
    "        return bisect_left(range(10**18), True, key=helper)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\r\n",
    "class Solution:\r\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\r\n",
    "        n = len(stations)\r\n",
    "        # change stations into a diff array of power\r\n",
    "        st = [0] * n\r\n",
    "        for i in range(n):\r\n",
    "            st[max(0, i - r)] += stations[i]\r\n",
    "            if i + r + 1 < n:\r\n",
    "                st[i + r + 1] -= stations[i]\r\n",
    "        # get power of each stations\r\n",
    "        for i in range(1, n):\r\n",
    "            st[i] += st[i - 1]\r\n",
    "        \r\n",
    "        # check whether we could power all stations no less than x\r\n",
    "        def check(x: int) -> bool:\r\n",
    "            p = k\r\n",
    "            q: deque[tuple[int, int]] = deque()\r\n",
    "            carry = 0\r\n",
    "            for i in range(n):\r\n",
    "                while q and q[0][0] == i:\r\n",
    "                    carry -= q[0][1]\r\n",
    "                    q.popleft()\r\n",
    "                if st[i] + carry >= x:\r\n",
    "                    continue\r\n",
    "                p -= x - st[i] - carry\r\n",
    "                if p < 0: return False\r\n",
    "                q.append((i + 2 * r + 1, x - st[i] - carry))\r\n",
    "                carry += x - st[i] - carry\r\n",
    "            return True\r\n",
    "                \r\n",
    "        lo = min(st)\r\n",
    "        hi = max(st) + k\r\n",
    "\r\n",
    "        while lo < hi:\r\n",
    "            mid = 1 + (lo + hi >> 1)\r\n",
    "            if check(mid):\r\n",
    "                lo = mid\r\n",
    "            else:\r\n",
    "                hi = mid - 1\r\n",
    "        \r\n",
    "        return lo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        # 二分查找\n",
    "        # 前缀和/滑窗\n",
    "        # 差分数组\n",
    "\n",
    "        # 前缀和\n",
    "        # [1,2,1,2]\n",
    "        # 前缀和数组为[0,1,3,4,6]\n",
    "        # 保证：子数组的和是两个前缀和的差，因此第一个元素是0\n",
    "\n",
    "        # 差分数组\n",
    "        # 比如给一个数组和多个操作，每次操作使得某个区间内的数都加1，操作完后看数组变成多少\n",
    "        # 笨办法：暴力\n",
    "        # 聪明做法：记录变化量，然后求前缀和\n",
    "        # [0,0,0,0,0]\n",
    "        # 中间三个数加1，[0,1,0,0,-1]\n",
    "        # 求前缀和：[0,1,1,1,0]就可以得到中间三个数加1的数组\n",
    "\n",
    "        # 每个城市的初始电量\n",
    "        # 可以用前缀和求\n",
    "        # 使最小供电站的数目尽可能大 -> 最大化最小值问题 -> 二分查找\n",
    "        # 看到「最大化最小值」或者「最小化最大值」就要想到二分答案，这是一个固定的套路。为什么？一般来说，二分的值越大，越能/不能满足要求；二分的值越小，越不能/能满足要求，有单调性，可以二分。\n",
    "\n",
    "        # ↓↓↓↓↓↓↓ \n",
    "        # 问题：在哪建电站\n",
    "        # 建在 min(i+r,n-1)处(中间区间处)\n",
    "        # 影响范围 [i,min(i+2r,n-1)]\n",
    "\n",
    "        n = len(stations)\n",
    "        # 构造前缀和\n",
    "        sum = list(accumulate(stations,initial=0))\n",
    "        # 初始电量\n",
    "        # 可以用前缀和求 \n",
    "        for i in range(n):\n",
    "            stations[i] = sum[min(i+r+1,n)] - sum[max(i-r,0)]\n",
    "\n",
    "        def check(min_power: int) -> bool:\n",
    "            diff = [0] * n\n",
    "            sum_d = need = 0\n",
    "            for i, power in enumerate(stations):\n",
    "                sum_d += diff[i]\n",
    "                delta = min_power - power - sum_d\n",
    "                if delta > 0:\n",
    "                    need += delta\n",
    "                    if need > k:\n",
    "                        return False\n",
    "                    sum_d += delta\n",
    "                    if i+2*r+1 < n:\n",
    "                        diff[i+2*r+1] -= delta\n",
    "            return True\n",
    "\n",
    "        # 二分查找搜索答案\n",
    "        left, right =  -1, sum[n] + k + 1\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid\n",
    "        return right-1 # 求最大值，即左边为True右边为False模型，返回left即可\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        nums = [0]*(n)\n",
    "        nums[0] = sum(stations[0:r+1])\n",
    "        for i in range(0, n-1):\n",
    "            nums[i + 1] = nums[i]\n",
    "            if i-r>=0:\n",
    "                nums[i+1] -= stations[i-r]\n",
    "            if i+1+r<n:\n",
    "                nums[i + 1] += stations[i+1+r]\n",
    "        def isValid(res:int) ->bool:\n",
    "            total = extra = 0\n",
    "            cf = [0]*n\n",
    "            for idx,num in enumerate(nums):\n",
    "                extra += cf[idx]\n",
    "                use = res - num - extra\n",
    "                if use>0:\n",
    "                    total += use\n",
    "                    if total>k:\n",
    "                        return False\n",
    "                    extra += use\n",
    "                    if idx+2*r+1<n:\n",
    "                        cf[idx+2*r+1] -= use\n",
    "            return True\n",
    "        left, right = 0, sum(stations)+k+1\n",
    "        while left<right:\n",
    "            mid = (left+right)>>1\n",
    "            if isValid(mid):\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left-1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        def key(limit):\n",
    "            diff = [0] * (len(stations) + r * 2 + 1)\n",
    "            for i, x in enumerate(stations):\n",
    "                diff[max(0, i - r)] += x\n",
    "                diff[i + r + 1] -= x\n",
    "\n",
    "            res = cur = 0\n",
    "            for i, _ in enumerate(stations):\n",
    "                cur += diff[i]\n",
    "                if cur < limit:\n",
    "                    res += limit - cur\n",
    "                    if res > k:\n",
    "                        return True\n",
    "                    diff[i + r * 2 + 1] -= (limit - cur)\n",
    "                    cur = limit\n",
    "            return res > k\n",
    "\n",
    "        return bisect_right(range(max(stations) * (r * 2 + 1) + k + 1), False, min(stations), key=key) - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        def key(limit):\n",
    "            diff = [0] * (len(stations) + r * 2 + 1)\n",
    "            for i, x in enumerate(stations):\n",
    "                diff[max(0, i - r)] += x\n",
    "                diff[i + r + 1] -= x\n",
    "\n",
    "            res = cur = 0\n",
    "            for i, _ in enumerate(stations):\n",
    "                cur += diff[i]\n",
    "                if cur < limit:\n",
    "                    res += limit - cur\n",
    "                    if res > k:\n",
    "                        return True\n",
    "                    diff[i + r * 2 + 1] -= (limit - cur)\n",
    "                    cur = limit\n",
    "            return res > k\n",
    "\n",
    "        return bisect_right(range(sum(stations) + k + 1), False, min(stations), key=key) - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def check(self,d:int,stations: List[int],prefix: List[int], r: int, k: int)->bool:\n",
    "\n",
    "        n = len(stations)\n",
    "\n",
    "        q = []\n",
    "\n",
    "        d_sum = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            left = max(i-r,0)\n",
    "            right = min(i+r+1,n)\n",
    "            while q and q[0][0]<left:\n",
    "                d_sum -= q[0][1]\n",
    "                heapq.heappop(q)\n",
    "            \n",
    "            if  d_sum + prefix[right] - prefix[left]<d:\n",
    "                add_d = d -  (d_sum + prefix[right] - prefix[left])\n",
    "                heapq.heappush(q,(i+r,add_d))\n",
    "                d_sum += add_d\n",
    "                k -= add_d\n",
    "                if k<0:\n",
    "                    return False\n",
    "        \n",
    "        return True\n",
    "        \n",
    "\n",
    "\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "\n",
    "        n = len(stations)\n",
    "\n",
    "        prefix = [0] * (n+1)\n",
    "\n",
    "        for i in range(n):\n",
    "            prefix[i+1] = prefix[i]+stations[i]\n",
    "\n",
    "        left = 0\n",
    "        right = prefix[n]+k\n",
    "\n",
    "        while left<right:\n",
    "            m = (left + right+1)//2\n",
    "            if self.check(m,stations,prefix,r,k):\n",
    "                left = m\n",
    "            else:\n",
    "                right = m - 1\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        def check():\n",
    "            q = collections.deque()\n",
    "            tmp = cnt = 0 # tmp: 当前多的数量\n",
    "            for i, x in enumerate(e_list):\n",
    "                # 先判断是否弹出\n",
    "                while q and q[0][0]<i-r:\n",
    "                    tmp -= q.popleft()[1]\n",
    "                if (c:=m+1-tmp-x) > 0:\n",
    "                    tmp += c\n",
    "                    cnt += c\n",
    "                    if cnt > k:\n",
    "                        return False\n",
    "                    q.append((i+r,c))\n",
    "            return True\n",
    "\n",
    "        n = len(stations)\n",
    "        e_list = []\n",
    "        e_min = inf\n",
    "        cur = sum(stations[:r])\n",
    "        for i in range(n):\n",
    "            if i+r <= n-1:\n",
    "                cur += stations[i+r]\n",
    "            if i-r-1 >= 0:\n",
    "                cur -= stations[i-r-1]\n",
    "            e_min = min(e_min, cur)\n",
    "            e_list.append(cur)\n",
    "        left, right = e_min, e_min + k\n",
    "        print(left, right, e_list)\n",
    "        while left <= right:\n",
    "            m = (left+right)//2\n",
    "            if check(): # 供m+1需要的新站小于等于k\n",
    "                left = m+1\n",
    "            else:\n",
    "                right = m-1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        s = [0]\n",
    "        n = len(stations)\n",
    "        for st in stations:\n",
    "            s.append(s[-1] + st)\n",
    "        for i in range(n):\n",
    "            stations[i] = s[min(n, i + r + 1)] - s[max(0, i - r)]\n",
    "        \n",
    "        def check(target):\n",
    "            diff = [0] * n\n",
    "            cur = 0\n",
    "            remain = k \n",
    "            for i in range(n):\n",
    "                cur += diff[i]\n",
    "                if cur + stations[i] < target:\n",
    "                    gap = target - cur - stations[i]\n",
    "                    if gap > remain:\n",
    "                        return False \n",
    "                    remain -= gap\n",
    "                    cur += gap\n",
    "                    if i + r + r + 1 < n:\n",
    "                        diff[i + r + r + 1] -= gap\n",
    "            return True \n",
    "\n",
    "        left = min(stations)\n",
    "        right = max(stations) + k \n",
    "        while left < right:\n",
    "            mid = left + (right - left) // 2 + 1\n",
    "            if not check(mid):\n",
    "                right = mid - 1 \n",
    "            else:\n",
    "                left = mid \n",
    "        return left \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        sum_power = [0] * (n+1)\n",
    "        for i in range(1,n+1):\n",
    "            sum_power[i] = stations[i-1] + sum_power[i-1]\n",
    "        for i in range(n):\n",
    "            stations[i] = sum_power[min(i+r+1,n)] - sum_power[max(i-r,0)]\n",
    "        \n",
    "        def check(min_power):\n",
    "            cur_k = 0\n",
    "            diff = [0]*n\n",
    "            add = 0\n",
    "            for i in range(n):\n",
    "                power = stations[i]\n",
    "                add += diff[i]\n",
    "                need = min_power - power - add\n",
    "                if need > 0:\n",
    "                    cur_k += need\n",
    "                    if cur_k > k:\n",
    "                        return cur_k\n",
    "                    add += need\n",
    "                    if i+2*r+1 < n:\n",
    "                        diff[i+2*r+1] -= need\n",
    "            return cur_k\n",
    "\n",
    "        left = min(stations)\n",
    "        right = min(stations) + k\n",
    "        while(right >= left):\n",
    "            cur = (right + left) // 2\n",
    "            cur_k = check(cur)\n",
    "            if cur_k == k:\n",
    "                return cur\n",
    "            if cur_k < k:\n",
    "                left = cur + 1\n",
    "            else:\n",
    "                right = cur - 1\n",
    "        return left - 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        sum = list(accumulate(stations, initial=0))  # 前缀和\n",
    "        for i in range(n):\n",
    "            stations[i] = sum[min(i + r + 1, n)] - sum[max(i - r, 0)]  # 电量\n",
    "\n",
    "        def check(min_power: int) -> bool:\n",
    "            diff = [0] * n  # 差分数组\n",
    "            sum_d = need = 0\n",
    "            for i, power in enumerate(stations):\n",
    "                sum_d += diff[i]  # 累加差分值\n",
    "                m = min_power - power - sum_d\n",
    "                if m > 0:  # 需要 m 个供电站\n",
    "                    need += m\n",
    "                    if need > k: return False  # 提前退出这样快一些\n",
    "                    sum_d += m  # 差分更新\n",
    "                    if i + r * 2 + 1 < n: diff[i + r * 2 + 1] -= m  # 差分更新\n",
    "            return True\n",
    "\n",
    "        left = min(stations)\n",
    "        right = left + k + 1  # 开区间写法\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid): left = mid\n",
    "            else: right = mid\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        sum = list(accumulate(stations, initial=0))  # 前缀和\n",
    "        for i in range(n):\n",
    "            stations[i] = sum[min(i + r + 1, n)] - sum[max(i - r, 0)]  # 电量\n",
    "\n",
    "        def check(min_power: int) -> bool:\n",
    "            diff = [0] * n  # 差分数组\n",
    "            sum_d = need = 0\n",
    "            for i, power in enumerate(stations):\n",
    "                sum_d += diff[i]  # 累加差分值\n",
    "                m = min_power - power - sum_d\n",
    "                if m > 0:  # 需要 m 个供电站\n",
    "                    need += m\n",
    "                    if need > k: return False  # 提前退出这样快一些\n",
    "                    sum_d += m  # 差分更新\n",
    "                    if i + r * 2 + 1 < n: diff[i + r * 2 + 1] -= m  # 差分更新\n",
    "            return True\n",
    "\n",
    "        left = min(stations)\n",
    "        right = left + k + 1  # 开区间写法\n",
    "        while left + 1 < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid): left = mid\n",
    "            else: right = mid\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n=len(stations)\n",
    "        pre=[0]*(n+1)\n",
    "        for i in range(n):\n",
    "            pre[i+1]=pre[i]+stations[i]\n",
    "        for i in range(n):\n",
    "            stations[i]=pre[min(i + r + 1,n)]-pre[max(i-r,0)]\n",
    "        #print(stations)\n",
    "        def check(x):\n",
    "            diff=[0]*n\n",
    "            now,need=0,0\n",
    "            for i,power in enumerate(stations):\n",
    "                now += diff[i]\n",
    "                m=x-power-now\n",
    "                if m>0:\n",
    "                    need+=m\n",
    "                    if need>k: \n",
    "                        return False\n",
    "                    now+=m\n",
    "                    if i+r*2+1<n: \n",
    "                        diff[i+r*2+1]-=m\n",
    "            return True\n",
    "        left=min(stations)\n",
    "        right=10**12\n",
    "        while left<right-1:\n",
    "            mid=(left+right)>>1\n",
    "            if check(mid): \n",
    "                left=mid\n",
    "            else: \n",
    "                right=mid\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        #最小供电站数目的最大值是多少,k确定放在哪些位置？\n",
    "        #k放在对最小值有影响的位置上？不应该如此放\n",
    "        #最小值很大，当前k无法满足;最小值很小，当前k还用不完,新建电站尽量建在右侧i+r的区域，统计r可以采用滑动窗口的办法进行\n",
    "        n = len(stations)\n",
    "        sum_ = list(accumulate(stations,initial=0))\n",
    "        for i in range(n):\n",
    "            stations[i] = sum_[min(i+r+1,n)] - sum_[max(i-r,0)]\n",
    "        \n",
    "        def check(min_power):\n",
    "            diff = [0] * n\n",
    "            sum_d = need = 0\n",
    "            for i, power in enumerate(stations):\n",
    "                sum_d += diff[i]\n",
    "                m = min_power - power - sum_d\n",
    "                if m>0:\n",
    "                    need += m\n",
    "                    if need>k:\n",
    "                        return False\n",
    "                    sum_d += m\n",
    "                    if i + r * 2 + 1< n:\n",
    "                        diff[i + r * 2 + 1] -= m\n",
    "            return True\n",
    "        \n",
    "        left = min(stations)\n",
    "        right = max(stations) + k + 1\n",
    "        while left<right:\n",
    "            mid = (left+right) // 2\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        s = [0]\n",
    "\n",
    "        for x in stations:\n",
    "            s.append(s[-1] + x)\n",
    "\n",
    "        for i in range(n):\n",
    "            stations[i] = s[min(n, i + r + 1)] - s[max(0, i - r)]\n",
    "\n",
    "        def check(x):\n",
    "            d = [0] * n\n",
    "            sum_d = need = 0\n",
    "            for i, p in enumerate(stations):\n",
    "                sum_d += d[i]\n",
    "                delta = x - sum_d - p\n",
    "                if delta > 0:\n",
    "                    need += delta\n",
    "                    if need > k:\n",
    "                        return False\n",
    "                    sum_d += delta\n",
    "                    if i + 2 * r + 1 < n:\n",
    "                        d[i + 2 * r + 1] -= delta\n",
    "            return True\n",
    "        \n",
    "\n",
    "        le, ri = 0, 10 ** 14\n",
    "        res = 0\n",
    "        while le <= ri:\n",
    "            mid = (le + ri) >> 1\n",
    "            if check(mid):\n",
    "                le = mid + 1\n",
    "                res = mid\n",
    "            else:\n",
    "                ri = mid - 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        if len(stations) == 1:\n",
    "            return stations[0] + k\n",
    "\n",
    "        pres = list(accumulate(stations,initial=0))\n",
    "        n = len(stations)\n",
    "\n",
    "        for i in range(n):\n",
    "            stations[i] = pres[min(i+r+1,n)] - pres[max(0,i-r)]\n",
    "\n",
    "        ll , rr = 0 , sum(stations)\n",
    "\n",
    "        def check(target):\n",
    "            s = 0\n",
    "            ans = 0\n",
    "            dist = [0] * (n+1)\n",
    "            for i , power in enumerate(stations):\n",
    "                s += dist[i]\n",
    "                t = target - s - power\n",
    "                if t > 0:\n",
    "                    ans += t\n",
    "                    if ans > k:return False\n",
    "                    s += t\n",
    "                    dist[min(n-1,i+2*r)+1] -= t\n",
    "            return True\n",
    "\n",
    "\n",
    "        while ll < rr:\n",
    "            mid = (ll + rr) >> 1\n",
    "            print(mid,check(mid))\n",
    "            if check(mid):\n",
    "                ll = mid + 1\n",
    "            else:\n",
    "                rr = mid\n",
    "        return ll if check(ll) else ll - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        psum = [0]\n",
    "        for i in range(len(stations)):\n",
    "            psum.append(psum[-1] + stations[i])\n",
    "        for i in range(len(stations)):\n",
    "            stations[i] = psum[min(i + r + 1, len(stations))] - psum[max(i - r, 0)]\n",
    "        left, right = 0, max(stations) + k\n",
    "        print(stations)\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            # print(left, right, mid)\n",
    "            diff = [0] * len(stations)\n",
    "            d = 0\n",
    "            can = True\n",
    "            cur = 0\n",
    "            for i in range(len(stations)):\n",
    "                d += diff[i]\n",
    "                if stations[i] + d < mid:\n",
    "                    need = mid - stations[i] - d\n",
    "                    # print(need, i, cur)\n",
    "                    if need + cur > k:\n",
    "                        can = False\n",
    "                        break\n",
    "                    cur += need                        \n",
    "                    d += need\n",
    "                    if i + 2 * r + 1 < len(stations):\n",
    "                        diff[i + 2 * r + 1] -= need\n",
    "            if can:\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left                                                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    #给定最小供电站数目，确定所需的最少供电站数目 \n",
    "    #如何确定所需最少的供电站数目了，可以使用贪心策略\n",
    "    #从左向右扫描每个城市，如果城市i的电量少于target,则补充该城市电量\n",
    "    #使用贪心策略时，最佳的补充的地方是i+r,因为i左侧的城市都已经大于等于target，所以要做i或者i的右侧补，而i+r这个位置能够覆盖范围最广\n",
    "\n",
    "    #因为频繁设计到对r范围内数字统一加减一个数字，所以可以使用差分数组提升效率\n",
    "    \n",
    "\n",
    "\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        \n",
    "        #使用前缀和来计算每个城市电量 accumulate函数可以计算前缀和，其是类加函数\n",
    "\n",
    "        n=len(stations)\n",
    "        pre_sum=list(accumulate(stations,initial=0))    # 相当于在station前面加了一个0，输出比输如多个0\n",
    "\n",
    "        for i in range(n):\n",
    "            stations[i]=pre_sum[min(n,i+r+1)]-pre_sum[max(0,i-r)]    #i+r+1 至 i-r的前缀和的差值刚好就是i的电量\n",
    "\n",
    "        #在给定最小电量的情况下，求至少要多少个电站\n",
    "        def minPower(target):\n",
    "            diff=[0]*n  #创建差分数组\n",
    "            diff[0]=stations[0]\n",
    "            for i in range(1,n):\n",
    "                diff[i]=stations[i]-stations[i-1]\n",
    "\n",
    "            cur_power=0   #当前位置的电量\n",
    "            need=0  #记录需要的电站数目\n",
    "            for i in range(n):\n",
    "                cur_power+=diff[i]    #利用差分累加的特性获取该点的电量\n",
    "\n",
    "                if_need=target-cur_power\n",
    "\n",
    "                if if_need>0:  #需要补充电量,依据贪心策略，在i+r的位置放电站，这个时候i-i+r-i+2r这个区间都要加相应的电量，因此i+2r+1位置处的差分值要-m\n",
    "                    need+=if_need\n",
    "                    cur_power+=if_need  #这个位置加m\n",
    "                    if i+2*r+1<n:diff[i+2*r+1]-=if_need\n",
    "            \n",
    "            return need   \n",
    "        return bisect_right(range(min(stations),min(stations)+k+1),k,key=minPower)+min(stations)-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        d = [0] * (n + 1)\n",
    "        for i, x in enumerate(stations):\n",
    "            d[max(0, i - r)] += x\n",
    "            d[min(n, i +r+1)] -= x\n",
    "        s = list(accumulate(d))[:-1]\n",
    "        \n",
    "        def check(min_p):\n",
    "            min_p += 1\n",
    "            diff = [0] * n\n",
    "            sum_d = need = 0\n",
    "            for i, x in enumerate(s):\n",
    "                sum_d += diff[i]\n",
    "                m = min_p - x - sum_d\n",
    "                if m > 0:\n",
    "                    need += m \n",
    "                    if need > k: return True\n",
    "                    sum_d += m \n",
    "                    if i + r * 2 + 1 < n:\n",
    "                        diff[i + r * 2 + 1] -= m \n",
    "            return False\n",
    "        \n",
    "        return bisect_left(range(sum(stations) + k), True, key=check)\n",
    "        # l = min(s)\n",
    "        # r = l + k + 1\n",
    "        # while l + 1 < r:\n",
    "        #     mid = (l + r) // 2\n",
    "        #     if check(mid):\n",
    "        #         l = mid \n",
    "        #     else:\n",
    "        #         r = mid \n",
    "        # return l "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        # check 函数，arr[i] 为第 i 个城市被多少供电站覆盖\n",
    "        # k 为还能建多少新供电站，t 为某个城市的最小供电站覆盖数\n",
    "        def check(arr, k, t):\n",
    "            diff = [0] * (n + 1)\n",
    "            # add 为有多少新建供电站覆盖当前位置 i\n",
    "            add = 0\n",
    "            for i, x in enumerate(arr):\n",
    "                # 差分，diff[i] 为 i - r - 1 位置建立的供电站所无法覆盖的边界\n",
    "                add += diff[i]\n",
    "                if add + x >= t: continue\n",
    "                # 遇到需要新建供电站时，不犹豫，直接拉到约束 t\n",
    "                # 但要贪心地将供电站建在 i + r 处保证新供电站作用最大化\n",
    "                cur = t - add - x\n",
    "                # 不够建了\n",
    "                if cur > k: return False\n",
    "                # 新供电站出现，给 add 加上，k 相应减去\n",
    "                add += cur\n",
    "                k -= cur\n",
    "                # 差分边界减去 cur 个供电站的贡献\n",
    "                diff[min(i + r + r + 1, n)] -= cur\n",
    "            return True\n",
    "        \n",
    "        n = len(stations)\n",
    "        diff = [0] * (n + 1)\n",
    "        # 算出初始状态的差分数组\n",
    "        for i, x in enumerate(stations):\n",
    "            L, R = max(i - r, 0), min(i + r + 1, n)\n",
    "            diff[L] += x\n",
    "            diff[R] -= x\n",
    "        # 对差分数组做前缀和，得到每个城市被多少供电站覆盖\n",
    "        pre = list(accumulate(diff[:-1]))\n",
    "        \n",
    "        # 二分答案，范围如下，右边界最大为 1e5 * 1e5 + 1e9 ==> 快进到 1e11\n",
    "        # 设想我们不建新供电站且覆盖半径 r = 0，此时答案是 min(stations)，因此可将 min(stations) + 1 作为左边界\n",
    "        # 本题的边界关键是右边界，若未给够，比方说答案是 1e10，但右边界给的 1e9，那么只能得到 1e9 这个上界\n",
    "        # 而左边界给 1 也是没问题的，因为 < min(stations) 的情况去 check 函数必定返回 true\n",
    "        # 整个区间映射到 check 函数后呈现为：\n",
    "        # [满足 | 最后一个满足（题目所求）| 第一个不满足 | 不满足]\n",
    "        # 由于我们要找的是最后一个满足的数字，因此找到第一个不满足的数字后减一即为最终结果\n",
    "        L, R = min(stations) + 1, int(1e11)\n",
    "        while L < R:\n",
    "            mid = (L + R) >> 1\n",
    "            if check(pre, k, mid):\n",
    "                L = mid + 1\n",
    "            else:\n",
    "                R = mid\n",
    "        return L - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        diff = [0]*(n+1)\n",
    "        for i,v in enumerate(stations):\n",
    "            L,R = max(0,i-r),min(i+r+1,n)\n",
    "            diff[L] += v\n",
    "            diff[R] -= v\n",
    "        stations = list(accumulate(diff[:-1]))\n",
    "        #print(stations)\n",
    "\n",
    "        def check(mx):\n",
    "            diff = [0]*(n+1)\n",
    "            dsum = 0\n",
    "            has = k\n",
    "            for i,v in enumerate(stations):\n",
    "                dsum += diff[i]\n",
    "                cur = v + dsum\n",
    "                need = mx-cur\n",
    "                if need > 0:\n",
    "                    if need > has:\n",
    "                        return False\n",
    "                    has -= need\n",
    "                    dsum += need\n",
    "                    diff[min(n,i+r+r+1)]-=need  \n",
    "            return True\n",
    "\n",
    "\n",
    "        \n",
    "        l,R = min(stations),min(stations)+k\n",
    "        while l < R:\n",
    "            mid = (l+R+1)>>1\n",
    "            if check(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                R = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        l = len(stations)\n",
    "        sumsta = [0] * l\n",
    "        s = sum(stations[:r+1])\n",
    "        for i in range(r):\n",
    "            sumsta[i] = s\n",
    "            if i+r+1 < l:s += stations[i+r+1]\n",
    "        for i in range(r,l-r):\n",
    "            sumsta[i] = s\n",
    "            if i+r+1 < l:s += stations[i+r+1]\n",
    "            if i-r >=0:s -= stations[i-r]\n",
    "        for i in range(l-r,l):\n",
    "            sumsta[i] = s\n",
    "            if i-r >=0:s -= stations[i-r]\n",
    "        def check(m):\n",
    "            L = [m] * l\n",
    "            for i in range(l):\n",
    "                if sumsta[i] >= m:L[i] = 0\n",
    "                else:L[i] -= sumsta[i]\n",
    "            cnt = 0\n",
    "            cur = 0\n",
    "            q = []\n",
    "            for idx,i in enumerate(L):\n",
    "                if q and q[0][0] < idx-2*r:\n",
    "                    o = heappop(q)\n",
    "                    cur -= o[1]\n",
    "                if i <= cur:continue\n",
    "                heappush(q,(idx,i-cur))\n",
    "                cnt += i-cur\n",
    "                cur = i\n",
    "            return cnt > k\n",
    "        return bisect_left(range(0,pow(10,15)),True,key = check)-1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        diff = [0] * (len(stations) + r * 2 + 1)\n",
    "        for i, x in enumerate(stations):\n",
    "            diff[max(0, i - r)] += x\n",
    "            diff[i + r + 1] -= x\n",
    "\n",
    "        def key(limit):\n",
    "            diff2 = diff[:]\n",
    "            res = cur = 0\n",
    "            for i, _ in enumerate(stations):\n",
    "                cur += diff2[i]\n",
    "                if cur < limit:\n",
    "                    res += limit - cur\n",
    "                    if res > k:\n",
    "                        return True\n",
    "                    diff2[i + r * 2 + 1] -= (limit - cur)\n",
    "                    cur = limit\n",
    "            return res > k\n",
    "\n",
    "        return bisect_right(range(sum(stations) + k + 1), False, min(stations), key=key) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        g = [0] * (n)\n",
    "        for i in range(n):\n",
    "            p = max(0,i - r)\n",
    "            g[p] += stations[i]\n",
    "            if i + r + 1 < n:\n",
    "                g[i + r + 1] -= stations[i]\n",
    "        for i in range(1,n):\n",
    "            g[i] += g[i - 1]  \n",
    "        def check(x):\n",
    "            st = [0] * n\n",
    "            t = k\n",
    "            for i in range(n):\n",
    "                if i > 0:\n",
    "                    st[i] += st[i - 1]  \n",
    "                if st[i] + g[i] < x:\n",
    "                    s = x - st[i] - g[i]\n",
    "                    t -= s\n",
    "                    if t < 0:\n",
    "                        return False\n",
    "                    st[i] += s\n",
    "                    if i + 2 * r + 1 < n:\n",
    "                        st[i + 2 * r + 1] -= s \n",
    "            return True   \n",
    "        low = 0\n",
    "        up = max(g) + k\n",
    "        while low <= up:\n",
    "            mid = low + up >> 1\n",
    "            if check(mid):\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                up = mid - 1\n",
    "        return up                  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        rr = r\n",
    "        preSum = [0]\n",
    "        cnt = 0\n",
    "        for s in stations:\n",
    "            cnt += s\n",
    "            preSum.append(cnt)\n",
    "        \n",
    "        powers = [0] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            powers[i] = preSum[min(i + r + 1, n)] - preSum[max(i - r, 0)]\n",
    "\n",
    "\n",
    "        l, r = 0, 10 ** 14\n",
    "\n",
    "        # with gived stations, r and k, the target m can be achieved?\n",
    "        def isValid(m: int) -> bool:\n",
    "            diff = [0] * (n + 1)\n",
    "            # to make the every city's power reach to m, add stations to the right border of each range\n",
    "            allCnt = 0\n",
    "            diffCnt = 0\n",
    "            for i in range(n):\n",
    "                diffCnt += diff[i] # have been added cnt in this city\n",
    "                cityPower = powers[i] + diffCnt\n",
    "                if cityPower < m: # have reached the target value\n",
    "                    allCnt += m - cityPower\n",
    "                    diffCnt += m - cityPower\n",
    "                    # update diff\n",
    "                    diff[min(i + 2*rr + 1, n)] -= m - cityPower\n",
    "                # print(diff)\n",
    "                # print(i, diffCnt, allCnt)\n",
    "            return allCnt <= k\n",
    "\n",
    "        while l < r:\n",
    "            m = (l + r + 1) >> 1\n",
    "            if isValid(m):\n",
    "                l = m\n",
    "            else:\n",
    "                r = m - 1\n",
    "        return l\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        #从左到右遍历，设本次猜的数为 c，遇到位置为 i处的电站小于 c ，则在 min(i+r,n−1) 处<临时>添加电站，也就是位于 [i,min⁡(i+2∗r,n−1)]的城市都增加了临时电站的覆盖    \n",
    "        # 寻找右边界\n",
    "        n = len(stations)\n",
    "        sum = list(accumulate(stations, initial=0))  # 前缀和\n",
    "        for i in range(n):\n",
    "            stations[i] = sum[min(i + r + 1, n)] - sum[max(i - r, 0)]  # 电量\n",
    "        diff = [0]*n\n",
    "        diff[0] = stations[0]\n",
    "        # 求差分数组\n",
    "        for i in range(1,n):\n",
    "            diff[i] +=stations[i] - stations[i-1] #原始diff\n",
    "        left = min(stations)\n",
    "        right = left + k + 1  # 开区间写法\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            res = self.f(mid,diff,k,n,r)\n",
    "            if res: left = mid+1\n",
    "            else: right = mid\n",
    "            # print(mid,res)\n",
    "        # print(left,right,mid)\n",
    "        return left-1\n",
    "\n",
    "\n",
    "    def f(self,x,diff,k,n,r):\n",
    "        # 需复制临时差分数组,不然会修改原数组\n",
    "        # print(diff,k,r,x)\n",
    "        tmp_diff = diff[:]\n",
    "        tmp_k = k\n",
    "        cur = 0\n",
    "        for i in range(n):\n",
    "            cur += tmp_diff[i] #当前i的座数\n",
    "            if cur < x:\n",
    "                need_k = x-cur\n",
    "                if need_k>tmp_k: #需要增加x-cur座电\n",
    "                    return False\n",
    "                tmp_k -= need_k\n",
    "                #则在i + r处增加x-cur,也就是need_k座，贪心\n",
    "                if (i+2*r+1)<n:\n",
    "                    tmp_diff[i+2*r+1] -=need_k\n",
    "                cur += need_k\n",
    "            # print(cur,tmp_diff,tmp_k)\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        #从左到右遍历，设本次猜的数为 c，遇到位置为 i处的电站小于 c ，则在 min(i+r,n−1) 处<临时>添加电站，也就是位于 [i,min⁡(i+2∗r,n−1)]的城市都增加了临时电站的覆盖    \n",
    "        # 寻找左边界\n",
    "        n = len(stations)\n",
    "        sum = list(accumulate(stations, initial=0))  # 前缀和\n",
    "        for i in range(n):\n",
    "            stations[i] = sum[min(i + r + 1, n)] - sum[max(i - r, 0)]  # 电量\n",
    "        diff = [0]*n\n",
    "        diff[0] = stations[0]\n",
    "        # 求差分数组\n",
    "        for i in range(1,n):\n",
    "            diff[i] +=stations[i] - stations[i-1] #原始diff\n",
    "        left = min(stations)\n",
    "        right = left + k + 1  # 开区间写法\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            res = self.f(mid,diff,k,n,r)\n",
    "            if res: left = mid+1\n",
    "            else: right = mid\n",
    "            # print(mid,res)\n",
    "        # print(left,right,mid)\n",
    "        return left-1\n",
    "\n",
    "\n",
    "    def f(self,x,diff,k,n,r):\n",
    "        # 需复制临时差分数组,不然会修改原数组\n",
    "        # print(diff,k,r,x)\n",
    "        tmp_diff = diff[:]\n",
    "        tmp_k = k\n",
    "        cur = 0\n",
    "        for i in range(n):\n",
    "            cur += tmp_diff[i] #当前i的座数\n",
    "            if cur < x:\n",
    "                need_k = x-cur\n",
    "                if need_k>tmp_k: #需要增加x-cur座电\n",
    "                    return False\n",
    "                tmp_k -= need_k\n",
    "                #则在i + r处增加x-cur,也就是need_k座，贪心\n",
    "                if (i+2*r+1)<n:\n",
    "                    tmp_diff[i+2*r+1] -=need_k\n",
    "                cur += need_k\n",
    "            # print(cur,tmp_diff,tmp_k)\n",
    "        return True\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        newStations = [0] * n\n",
    "        prefixSum = [0] + list(accumulate(stations))\n",
    "        for i in range(n):\n",
    "            lower = max(0, i - r)\n",
    "            upper = min(i + r, n - 1)\n",
    "            newStations[i] = prefixSum[upper + 1] - prefixSum[lower]\n",
    "\n",
    "        # print(newStations)\n",
    "        def canPowerup(minimum):\n",
    "            diff = [0] * n\n",
    "            diff[0] = newStations[0]\n",
    "            for i in range(1, n):\n",
    "                diff[i] = newStations[i] - newStations[i-1]\n",
    "\n",
    "            sumOfDiff = 0\n",
    "            addition = 0\n",
    "            for i in range(n):\n",
    "                sumOfDiff += diff[i]\n",
    "                delta = minimum - sumOfDiff\n",
    "                if delta > 0:\n",
    "                    sumOfDiff += delta\n",
    "                    diff[i] += delta\n",
    "                    addition += delta\n",
    "                    if addition > k:\n",
    "                        return False\n",
    "                    nextIdx = i + 2 * r + 1\n",
    "                    # diff[i] += delta\n",
    "                    # diff[nextIdx] -= delta\n",
    "                    # equals to tmp[i:nextIndex-1] += delta\n",
    "                    if nextIdx < n:\n",
    "                        diff[nextIdx] -= delta\n",
    "            # print(minimum, addition)\n",
    "            return addition <= k\n",
    "\n",
    "        \n",
    "        left = min(newStations)\n",
    "        right = left + k + 1\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if canPowerup(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left - 1\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        prefix = list(accumulate(stations, initial=0))\n",
    "        A = [prefix[min(i+r, n-1)+1]-prefix[max(i-r, 0)] for i in range(n)]\n",
    "        MIN = min(A)\n",
    "        left, right = MIN, MIN+k\n",
    "        # print(prefix)\n",
    "        # print(A)\n",
    "\n",
    "        def check(mid):\n",
    "            cnt = 0\n",
    "            diff = [0] * (n+1)\n",
    "\n",
    "            for i in range(n):\n",
    "                diff[i] += diff[i-1]\n",
    "                cur = A[i] + diff[i]\n",
    "                if cur < mid:\n",
    "                    less = mid-cur\n",
    "                    cnt += less\n",
    "                    diff[i] += less\n",
    "                    diff[min(i+r*2+1, n)] -= less\n",
    "            return cnt <= k\n",
    "        while left <= right:\n",
    "            mid = (left + right) >> 1\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "from bisect import bisect_left\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        power = list(accumulate(stations,initial=0))\n",
    "        stotal = []\n",
    "        for i in range(n):\n",
    "            stotal.append(power[min(n,i+r+1)]-power[max(0,i-r)])\n",
    "        def boo(mid):\n",
    "            diff = [0]*n\n",
    "            d = 0\n",
    "            to = 0\n",
    "            for i in range(n):\n",
    "                new = mid - stotal[i]-d\n",
    "                if new >0:\n",
    "                    to+=new\n",
    "                    if to > k:\n",
    "                        return True\n",
    "                    diff[i] += new\n",
    "                    if i+2*r < n:\n",
    "                        diff[i+2*r] -= new\n",
    "                d += diff[i]\n",
    "            return False\n",
    "        l = min(stotal)\n",
    "        ri = l+k+1\n",
    "        # for i in range(l,ri):\n",
    "            # print(f'As i is {i}, boo is {boo(i)}, ')\n",
    "        ans = bisect_left(range(l,ri),True,key= boo) \n",
    "        print(ans)\n",
    "        return ans+l-1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        #二分答案+贪心+差分数组+前缀和\n",
    "        n = len(stations)\n",
    "        sum = list(accumulate(stations,initial = 0))\n",
    "        ele = [0]*n\n",
    "        for i in range(n):\n",
    "            ele[i] = sum[min(n,i+r+1)]-sum[max(0,i-r)]\n",
    "        #二分答案\n",
    "        def check(lim:int,cnt:int)->bool:\n",
    "            diff = [0]*n\n",
    "            sumD = 0\n",
    "            for i in range(n):\n",
    "                #贪心，考虑能辐射的范围自左向右为2*r+1\n",
    "                high = min(n,i+r*2+1)\n",
    "                sumD+=diff[i]\n",
    "                x = ele[i]+sumD\n",
    "                if x>=lim:continue\n",
    "                if cnt <= 0:return False\n",
    "                sub = lim-x\n",
    "                cnt-=sub\n",
    "                if cnt<0:return False\n",
    "                sumD+=sub\n",
    "                if high<n:\n",
    "                    diff[high]-=sub         \n",
    "            return True\n",
    "\n",
    "        left,right = 0,min(ele)+k\n",
    "        while left<right:\n",
    "            mid = (left+right+1)>>1\n",
    "            if check(mid,k):left = mid\n",
    "            else:right = mid-1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: [int], r: int, k: int) -> int:\n",
    "        nm=len(stations)\n",
    "        diff=[0 for i in range(nm+1)]\n",
    "        for i in range(nm):\n",
    "            if stations[i]>0:\n",
    "                left=max(0,i-r)\n",
    "                right=min(nm-1,i+r)\n",
    "                diff[left]+=stations[i]\n",
    "                diff[right+1]-=stations[i]\n",
    "\n",
    "#        print(diff)\n",
    "        nums=[0 for i in range(nm)]\n",
    "        tot=0\n",
    "        for i in range(nm):\n",
    "            tot+=diff[i]\n",
    "            nums[i]=tot\n",
    "#        print(nums)\n",
    "\n",
    "        def check(mid:int,k:int):\n",
    "            mydiff=diff[:]\n",
    "            mynums=[0]*(nm+1)\n",
    "\n",
    "            ans, revCnt = 0, 0\n",
    "            for i in range(nm):\n",
    "                revCnt += mydiff[i]  # 到达第i位的时候， 需要操作 diff[i]次， 其实就是前缀和到了多少\n",
    "                if revCnt<mid:      #当前站不够的话\n",
    "                    XXX = mid-revCnt  # 是否需要是 负号？ ?\n",
    "                    ans += XXX  # 翻转次数  ，  也即 XXXX\n",
    "                    if ans>k:\n",
    "                        return False\n",
    "                    revCnt += XXX  # 左侧位置+1 直接传递到 revCnt 上\n",
    "                    maxed=min(nm-1,i+2*r)\n",
    "                    mydiff[maxed+1] -= XXX  # 右端点+1 位置 -1\n",
    "            return True\n",
    "\n",
    "        left=min(nums)\n",
    "        right=left+k\n",
    "        res=left\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid,k):          #二分法判断是否符合条件\n",
    "                left=mid+1\n",
    "                res=mid\n",
    "            else:\n",
    "                right=mid-1               #符合条件，记录当前的阈值\n",
    "        return res\n",
    "\n",
    "stations = [1,2,4,5,0,1,2,3,4,5]\n",
    "r = 1\n",
    "k = 2\n",
    "print(Solution().maxPower(stations,r,k))\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        \n",
    "        cnts = []\n",
    "        pre_sum = [0] * (n + 1)\n",
    "        for i in range(1, n + 1):\n",
    "            pre_sum[i] = pre_sum[i - 1] + stations[i - 1]\n",
    "\n",
    "        for i in range(n):\n",
    "            left = max(0, i - r)\n",
    "            right = min(n, i + r + 1)\n",
    "            cnts.append(pre_sum[right] - pre_sum[left])\n",
    "        \n",
    "        def check(x):\n",
    "            arr = cnts.copy()\n",
    "            ans = 0\n",
    "            diffs = [0] * (n + 1)\n",
    "            status = 0\n",
    "            for i in range(n):\n",
    "                status += diffs[i]\n",
    "                if cnts[i] + status < x:\n",
    "                    diff = x - (cnts[i] + status)\n",
    "                    ans += diff\n",
    "                    diffs[min(i + 2 * r + 1, n)] -= diff\n",
    "                    status += diff\n",
    "            return ans <= k\n",
    "                    \n",
    "    \n",
    "        left, right = 0, sum(stations) + k + 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return int(left) - 1\n",
    "        \n",
    "\n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        pre = [0] * (n + 1)\n",
    "        for i in range(n): pre[i + 1] = pre[i] + stations[i]\n",
    "        stations = [pre[min(i + r, n)] - pre[max(0, i - r - 1)] for i in range(1, n + 1)]\n",
    "\n",
    "        def check(t):\n",
    "            diff = [0] * n\n",
    "            s = need = 0\n",
    "            for i in range(n):\n",
    "                s += diff[i]\n",
    "                m = t - stations[i] - s\n",
    "                if m > 0:\n",
    "                    need += m\n",
    "                    if need > k: return False\n",
    "                    s += m\n",
    "                    if i + 2 * r + 1 < n: diff[i + 2 * r + 1] -= m\n",
    "            return True\n",
    "\n",
    "        left = min(stations)\n",
    "        right = left + k\n",
    "        while left < right:\n",
    "            mid = left + right + 1 >> 1\n",
    "            if check(mid): left = mid\n",
    "            else: right = mid - 1\n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        g = [0] * (n)\n",
    "        for i in range(n):\n",
    "            p = max(0,i - r)\n",
    "            g[p] += stations[i]\n",
    "            if i + r + 1 < n:\n",
    "                g[i + r + 1] -= stations[i]\n",
    "        for i in range(1,n):\n",
    "            g[i] += g[i - 1]\n",
    "        print(g)    \n",
    "        def check(x):\n",
    "            st = [0] * n\n",
    "            t = k\n",
    "            for i in range(n):\n",
    "                if i > 0:\n",
    "                    st[i] += st[i - 1]  \n",
    "                if st[i] + g[i] < x:\n",
    "                    s = x - st[i] - g[i]\n",
    "                    t -= s\n",
    "                    if t < 0:\n",
    "                        return False\n",
    "                    st[i] += s\n",
    "                    if i + 2 * r + 1 < n:\n",
    "                        st[i + 2 * r + 1] -= s \n",
    "            return True   \n",
    "        low = 0\n",
    "        up = max(g) + k\n",
    "        while low <= up:\n",
    "            mid = low + up >> 1\n",
    "            if check(mid):\n",
    "                low = mid + 1\n",
    "            else:\n",
    "                up = mid - 1\n",
    "        return up                  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        def check(m):\n",
    "            res,s,n=0,0,len(stations)\n",
    "            diff=[0]*n\n",
    "            for i in range(n):\n",
    "                s+=diff[i]\n",
    "                cur=prefix[min(n,i+r+1)]-prefix[max(0,i-r)]+s\n",
    "                if cur<m:\n",
    "                    res+=m-cur\n",
    "                    s+=m-cur\n",
    "                    if i+2*r+1<n: diff[i+2*r+1]-=m-cur\n",
    "            return res\n",
    "\n",
    "        prefix=[0]\n",
    "        for n in stations:\n",
    "            prefix.append(prefix[-1]+n)\n",
    "\n",
    "        left,right=0,sum(stations)+k\n",
    "        while left<right:\n",
    "            m=(left+right+1)>>1\n",
    "            if check(m)>k: right=m-1\n",
    "            else: left=m\n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        s = list(accumulate(stations, initial = 0))  # 前缀和的简便写法\n",
    "        memo = [0 for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            memo[i] = s[min(i + r + 1, n)] - s[max(i - r, 0)]\n",
    "        \n",
    "        left = min(memo)\n",
    "        right = min(memo) + k\n",
    "        while left < right:\n",
    "            mid = (right - left + 1) // 2 + left\n",
    "            if self.check(n, r, k, mid, memo):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return left\n",
    "\n",
    "\n",
    "    def check(self, n, r, k, mid, memo):\n",
    "        diff = [0] * n  # 差分数组\n",
    "        sum_d = cnt = 0\n",
    "        for i in range(n):\n",
    "            sum_d += diff[i]  # 累加差分值\n",
    "            cur = mid - memo[i] - sum_d\n",
    "            if cur > 0:\n",
    "                cnt += cur\n",
    "                if cnt > k: return False\n",
    "                sum_d += cur  # 差分更新\n",
    "                if i + r*2 + 1 < n: diff[i+r*2+1] -= cur\n",
    "        # print(mid, memo, cnt, k)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "\n",
    "        n = len(stations)\n",
    "        pos = [0]\n",
    "        now = 0\n",
    "        for i, num in enumerate(stations):\n",
    "            now += num\n",
    "            pos.append(now)\n",
    "        \n",
    "        stk = [0] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            left = max(0, i-r)\n",
    "            right = min(n, i+r+1)\n",
    "            stk[i] = pos[right] - pos[left]\n",
    "\n",
    "        def slove(t):\n",
    "            \n",
    "            diff = [0] * (n)\n",
    "            cha = 0\n",
    "            now = 0\n",
    "            for i,num in enumerate(stk):\n",
    "                now += diff[i]\n",
    "\n",
    "                if (now + num) < t:\n",
    "                    cha += t - (now+num)\n",
    "                    if cha > k :\n",
    "                        return False\n",
    "                    diff[i] += t-(now+num)\n",
    "                    if i + r * 2 + 1 < n:\n",
    "                        diff[i+r*2+1] -= t - (now+num)  \n",
    "                    now += t-(now+num)\n",
    "\n",
    "            return True\n",
    "\n",
    "        left = 0\n",
    "        right = int(1e12)\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left+right) >> 1\n",
    "            if slove(mid):\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        preSum = [0] * n\n",
    "        for i, v in enumerate(stations):\n",
    "            preSum[i] = preSum[i - 1] + v\n",
    "        \n",
    "        power = [0] * n\n",
    "        for i, v in enumerate(preSum):\n",
    "            if i - r - 1 >= 0:\n",
    "                power[i] = preSum[min(i + r, n - 1)] - preSum[i - r - 1]\n",
    "            else:\n",
    "                power[i] = preSum[min(i + r, n - 1)]\n",
    "        \n",
    "        left = min(power)\n",
    "        right = max(power) + k\n",
    "\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            diff = [0] * n\n",
    "            sum_d = need = 0\n",
    "            condition = True\n",
    "            for i, p in enumerate(power):\n",
    "                sum_d += diff[i]\n",
    "                # 不够\n",
    "                if sum_d + p < mid:\n",
    "                    build = mid - p - sum_d\n",
    "                    need += build\n",
    "                    if need > k:\n",
    "                        condition = False\n",
    "                        break\n",
    "                    sum_d += build\n",
    "                    if i + 2 * r + 1 < n:\n",
    "                        diff[i + 2 * r + 1] = -build\n",
    "            \n",
    "            if condition:\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        sum_list = list(accumulate(stations, initial=0))\n",
    "        \n",
    "        cur_s = []\n",
    "        n = len(stations)\n",
    "        for i, sta in enumerate(stations):\n",
    "            left = sum_list[i] - sum_list[max(0, i-r)]\n",
    "            right = sum_list[min(i+r+1, n)] - sum_list[i+1]\n",
    "            cur_s.append(sta + left + right)\n",
    "\n",
    "        def helper(mid):\n",
    "            diff = [0] * (n+1)\n",
    "            cur_sum = 0\n",
    "            cur_res = 0\n",
    "            for i, cur in enumerate(cur_s):\n",
    "                cur_sum += diff[i]\n",
    "                if cur + cur_sum < mid:\n",
    "                    gap = mid - cur - cur_sum\n",
    "                    cur_sum += gap\n",
    "                    cur_res += gap\n",
    "                    diff[min(n, i + 2*r + 1)] -= gap\n",
    "\n",
    "                if cur_res > k:\n",
    "                    return False\n",
    "                    \n",
    "            return cur_res <= k\n",
    "\n",
    "        left, right = 0, max(cur_s) + k\n",
    "        while left < right:\n",
    "            mid = (left+right) // 2\n",
    "            if helper(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        if helper(left):\n",
    "            return left\n",
    "        return left - 1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        sum_list = list(accumulate(stations, initial=0))\n",
    "        \n",
    "        cur_s = []\n",
    "        n = len(stations)\n",
    "        for i, sta in enumerate(stations):\n",
    "            left = sum_list[i] - sum_list[max(0, i-r)]\n",
    "            right = sum_list[min(i+r+1, n)] - sum_list[i+1]\n",
    "            cur_s.append(sta + left + right)\n",
    "\n",
    "        def helper(mid):\n",
    "            diff = [0] * (n+1)\n",
    "            cur_sum = 0\n",
    "            cur_res = 0\n",
    "            for i, cur in enumerate(cur_s):\n",
    "                cur_sum += diff[i]\n",
    "                if cur + cur_sum < mid:\n",
    "                    gap = mid - cur - cur_sum\n",
    "                    diff[i] += gap\n",
    "                    cur_sum += gap\n",
    "                    cur_res += gap\n",
    "                    diff[min(n, i + 2*r + 1)] -= gap\n",
    "                    \n",
    "            return cur_res <= k\n",
    "\n",
    "        left, right = 0, max(cur_s) + k\n",
    "        while left < right:\n",
    "            mid = (left+right) // 2\n",
    "            if helper(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        if helper(left):\n",
    "            return left\n",
    "        return left - 1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n=len(stations) # stations 中城市数量\n",
    "\n",
    "        sum=list(accumulate(stations)) #累计和\n",
    "        st_accpower=[0]*n # 按照题目规则，存储当前各城市r距离辐射范围内的电站数\n",
    "        for i in range(n): \n",
    "            if i-r-1 >=0:\n",
    "                st_accpower[i]=sum[min(i+r,n-1)] -sum[i-r-1]\n",
    "            else:\n",
    "                st_accpower[i]=sum[min(i+r,n-1)]\n",
    "        print(sum)\n",
    "        print(st_accpower)\n",
    "        def accept(min_power): #判断min_power是否比所有城市辐射范围内的电站数更大 \n",
    "            used=0     #已使用新增电站个数\n",
    "            diff=[0]*n #差分数组，相比于前一个城市，i城市辐射内新增电站数\n",
    "            sum_d=0    #累计差分值\n",
    "            for i in range(len(st_accpower)):\n",
    "                sum_d +=diff[i]\n",
    "                tmp = min_power -(st_accpower[i]+sum_d)\n",
    "                if tmp>0: #如果min_power比当前城市的辐射供电站多，需要通过建站补齐\n",
    "                    used += tmp #已使用电站+tmp\n",
    "                    if used >k: return False #需要的新增站点数超过k\n",
    "                    sum_d += tmp #累计差分+tmp。此处隐含了diff[i]+=tmp，由于后续已经用不到了，所以可以不做更新\n",
    "                    # 注意，这里是关键的一步\n",
    "                    if i+2*r+1<n: #由于 i左侧的不需要补足，所以贪心地在 min⁡(i+r,n−1) 处建是最合适的，恰好让 i 在覆盖范围的边界上，此时右边界为i+2*r，差分数组需要在i+2*r+1处减去tmp。\n",
    "                        diff[i+2*r+1]-=tmp\n",
    "            return True #以上部分都满足了，说明min_power符合条件\n",
    "      \n",
    "        # #使用二分查找，不断探索min_power的合理值\n",
    "        left = min(st_accpower)\n",
    "        right = left+k+1\n",
    "        while left <right:\n",
    "            mid=(left+right)//2\n",
    "            print(left,right)\n",
    "            if accept(mid): #mid偏小\n",
    "                left=mid+1\n",
    "            else: #mid偏大\n",
    "                right=mid\n",
    "        return left-1  #left=right时，left偏大，所以需要-1处理\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        arr = [0] * n\n",
    "\n",
    "        cur = sum(stations[:r])\n",
    "        stations = [0] * r + stations + [0] * r\n",
    "        \n",
    "        for i in range(r, r+n):\n",
    "            cur += stations[i+r]\n",
    "            arr[i-r] = cur\n",
    "            cur -= stations[i-r]\n",
    "\n",
    "        diff = [0] * (n + 1)\n",
    "        diff[0] = arr[0]\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            diff[i] = arr[i] - arr[i-1]\n",
    "        \n",
    "        def is_valid(x) -> bool:\n",
    "            tmp = diff.copy()\n",
    "            cnt = k\n",
    "            cur = 0\n",
    "\n",
    "            for i in range(n):\n",
    "                cur += tmp[i]\n",
    "                if (gap := x - cur) <= 0:\n",
    "                    continue\n",
    "                \n",
    "                if cnt < gap:\n",
    "                    return False\n",
    "                cnt -= gap\n",
    "                \n",
    "                cur += gap\n",
    "                tmp[min(i+r*2+1, n)] -= gap\n",
    "            \n",
    "            return True\n",
    "\n",
    "        left  = min(arr)\n",
    "        right = left + k\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) >> 1\n",
    "            if is_valid(mid):\n",
    "                left  = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n=len(stations)\n",
    "        diff=[0]*n\n",
    "        for i in range(n):\n",
    "            diff[max(i-r,0)]+=stations[i]\n",
    "            if (i+r+1)>n-1:\n",
    "                pass\n",
    "            else:\n",
    "                diff[i+r+1]-=stations[i]\n",
    "        sum1=0\n",
    "        ans=[]\n",
    "        for i in range(n):\n",
    "            sum1+=diff[i]\n",
    "            ans.append(sum1)\n",
    "        left=min(ans)\n",
    "        right=left+k+1\n",
    "\n",
    "        def check(x,k):\n",
    "            n=len(stations)\n",
    "            diff=[0]*n\n",
    "            for i in range(n):\n",
    "                diff[max(i-r,0)]+=stations[i]\n",
    "                if (i+r+1)>n-1:\n",
    "                    pass\n",
    "                else:\n",
    "                    diff[i+r+1]-=stations[i]\n",
    "            sum1=0\n",
    "            for i in range(n):\n",
    "                sum1+=diff[i]\n",
    "                if sum1<x:\n",
    "                    t=x-sum1\n",
    "                    loc=min(i+r,n-1)\n",
    "                    sum1+=t\n",
    "                    if loc+r+1>n-1:\n",
    "                        pass\n",
    "                    else:\n",
    "                        diff[loc+r+1]-=t\n",
    "                    k=k-t\n",
    "                   \n",
    "            if k<0:\n",
    "                # print(k)\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "\n",
    "        # print(check(52,23))\n",
    "       \n",
    "        while left+1<right:\n",
    "            mid=(left+right)//2\n",
    "            if check(mid,k):\n",
    "                left=mid\n",
    "            else:\n",
    "                right=mid\n",
    "        return left\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n=len(stations) # stations 中城市数量\n",
    "\n",
    "        sum=list(accumulate(stations)) #累计和\n",
    "        st_accpower=[0]*n # 按照题目规则，存储当前各城市r距离辐射范围内的电站数\n",
    "        for i in range(n): \n",
    "            if i-r-1 >=0:\n",
    "                st_accpower[i]=sum[min(i+r,n-1)] -sum[i-r-1]\n",
    "            else:\n",
    "                st_accpower[i]=sum[min(i+r,n-1)]\n",
    "        print(sum)\n",
    "        print(st_accpower)\n",
    "        def accept(min_power): #判断min_power是否比所有城市辐射范围内的电站数更大 \n",
    "            used=0     #已使用新增电站个数\n",
    "            diff=[0]*n #差分数组，相比于前一个城市，i城市辐射内新增电站数\n",
    "            sum_d=0    #累计差分值\n",
    "            for i in range(len(st_accpower)):\n",
    "                sum_d +=diff[i]\n",
    "                tmp = min_power -(st_accpower[i]+sum_d)\n",
    "                if tmp>0: #如果min_power比当前城市的辐射供电站多，需要通过建站补齐\n",
    "                    used += tmp #已使用电站+tmp\n",
    "                    if used >k: return False #需要的新增站点数超过k\n",
    "                    sum_d += tmp #累计差分+tmp。此处隐含了diff[i]+=tmp，由于后续已经用不到了，所以可以不做更新\n",
    "                    # 注意，这里是关键的一步\n",
    "                    if i+2*r+1<n: #由于 i左侧的不需要补足，所以贪心地在 min⁡(i+r,n−1) 处建是最合适的，恰好让 i 在覆盖范围的边界上，此时右边界为i+2*r，差分数组需要在i+2*r+1处减去tmp。\n",
    "                        diff[i+2*r+1]-=tmp\n",
    "            return True #以上部分都满足了，说明min_power符合条件\n",
    "      \n",
    "        # #使用二分查找，不断探索min_power的合理值\n",
    "        # left = min(st_accpower)\n",
    "        # right = left+k+1\n",
    "        # while left <right:\n",
    "        #     mid=(left+right)//2\n",
    "        #     if accept(mid):\n",
    "        #         right=mid-1\n",
    "        #     else:\n",
    "        #         left=mid\n",
    "        # return left\n",
    "\n",
    "        left=min(st_accpower)\n",
    "        right=left+k+1\n",
    "        while left +1 < right:\n",
    "            mid=(left+right)//2\n",
    "            if accept(mid): #偏大\n",
    "                left=mid\n",
    "            else:          #偏小或刚好\n",
    "                right=mid\n",
    "        return left\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        s = [0] * n\n",
    "        pre = [0]\n",
    "        for i in range(n):\n",
    "            pre.append(pre[-1] + stations[i])\n",
    "        for i in range(n):\n",
    "            s[i] = pre[min(n,i+r+1)] - pre[max(0,i-r)]\n",
    "\n",
    "        def isTure(x):\n",
    "            kk = k\n",
    "            ss = s[:]\n",
    "            st = [0] * (n+1)\n",
    "            a = 0\n",
    "            for i in range(n):\n",
    "                a += st[i]\n",
    "                ss[i] += a\n",
    "                if ss[i] < x:\n",
    "                    a += x - ss[i]\n",
    "                    kk -= x - ss[i]\n",
    "                    st[min(n,i + 2 * r + 1)] -= (x - ss[i])\n",
    "                if kk < 0:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        ma = pre[-1] + k\n",
    "        mi = 0\n",
    "        mid = (ma - mi) // 2 + mi\n",
    "        while mi <mid< ma:\n",
    "            if isTure(mid):\n",
    "                mi = mid\n",
    "            else:\n",
    "                ma = mid\n",
    "            mid = (ma - mi) // 2 + mi\n",
    "        if isTure(ma):\n",
    "            return ma\n",
    "        if isTure(mid):\n",
    "            return mid\n",
    "        return mi\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "\n",
    "        m = len(stations)\n",
    "        cnt = [0] * m\n",
    "        \n",
    "        diff = deque()\n",
    "        diff_sum = 0\n",
    "        for i in range(-r, m):\n",
    "            \n",
    "            if i+r < m:\n",
    "                diff.append([i, stations[i+r]])\n",
    "                diff_sum += stations[i+r]\n",
    "            while diff and i-diff[0][0] > 2*r:\n",
    "                diff_sum -= diff.popleft()[1]\n",
    "            if i >= 0:\n",
    "                cnt[i] = diff_sum\n",
    "\n",
    "        #print(cnt)\n",
    "        \n",
    "        left = min(cnt)\n",
    "        right = max(cnt) + k\n",
    "        \n",
    "        while left < right:\n",
    "            \n",
    "            mid = (left + right + 1) // 2\n",
    "            #print(left, right,mid)\n",
    "            s = 0\n",
    "            diff = deque()\n",
    "            diff_sum = 0\n",
    "            for i, n in enumerate(cnt):\n",
    "                while diff and i - diff[0][0] > 2*r:\n",
    "                    diff_sum -= diff.popleft()[1]\n",
    "                n += diff_sum\n",
    "                if n >= mid:\n",
    "                    continue\n",
    "                \n",
    "                \n",
    "                s += mid-n\n",
    "                if s > k:\n",
    "                    right = mid - 1\n",
    "                    break\n",
    "                diff_sum += mid - n\n",
    "                diff.append([i, mid-n])\n",
    "                    \n",
    "                    \n",
    "            else:\n",
    "\n",
    "                left = mid\n",
    "            #print('-->', s)\n",
    "\n",
    "            \n",
    "            \n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        low = 0; up = 100000000000000\n",
    "        maxr = 2*r+1\n",
    "        ls = [0]\n",
    "        ls[0] = sum(stations[0:r+1])\n",
    "        cnt = r + 1\n",
    "        s = ls[0]\n",
    "        for i in range(1, len(stations)):\n",
    "            if i + r < len(stations):\n",
    "                s += stations[i+r]\n",
    "            cnt += 1\n",
    "            if cnt > 2*r+1:\n",
    "                s -= stations[i-r-1]\n",
    "                cnt -= 1\n",
    "            ls.append(s)\n",
    "        print(ls)\n",
    "        \n",
    "        def check(tg):\n",
    "            d = defaultdict(int)\n",
    "            s = 0\n",
    "            remain = k\n",
    "            for i in range(len(ls)):\n",
    "                if ls[i] + s >= tg:\n",
    "                    if i - r in d:\n",
    "                        s -= d[i-r]\n",
    "                    continue\n",
    "                diff = tg - ls[i] - s\n",
    "                if remain < diff:\n",
    "                    return False\n",
    "                pos = min(len(ls)-1, i+r)\n",
    "                d[pos] += diff\n",
    "                s += diff\n",
    "                remain -= diff\n",
    "                # if tg == 149:\n",
    "                #     print(i,d,s,remain)\n",
    "                if i - r in d:\n",
    "                    s -= d[i-r]\n",
    "            return True\n",
    "            \n",
    "        \n",
    "        while low <= up:\n",
    "            m = (low+up)//2\n",
    "            if check(m):\n",
    "                low = m + 1\n",
    "            else:\n",
    "                up = m - 1\n",
    "        return low - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        pre = [0]*(n+1)\n",
    "        for i in range(1, n+1):\n",
    "            pre[i] = pre[i-1]+stations[i-1]\n",
    "        stations2 = [0]*n\n",
    "        for i in range(n):\n",
    "            left = max(0, i-r)\n",
    "            right = min(n-1, i+r)\n",
    "            stations2[i] = pre[right+1]-pre[left]\n",
    "\n",
    "        def check(min_power):\n",
    "            diff = [0]*(n+1) # 防止差分越界\n",
    "            diff[0] = stations2[0]\n",
    "            for i in range(1, n):\n",
    "                diff[i] = stations2[i]-stations2[i-1]\n",
    "            sd = 0 # 到i的累加值，即stations2[i] 增加发电站后的值\n",
    "            need = 0 # 累计增加的供电站数量\n",
    "            for i, power in enumerate(stations2):\n",
    "                sd += diff[i]\n",
    "                m_d = min_power - sd\n",
    "                if m_d>0: # 需要增加m个供电站\n",
    "                    need+=m_d \n",
    "                    if need>k:\n",
    "                        return False\n",
    "                    # [i+r]位置建立m_d个供电站，覆盖范围[i, i+2r]\n",
    "                    diff[i]+=m_d\n",
    "                    sd+=m_d \n",
    "                    right = min(n-1, i+2*r)\n",
    "                    diff[right+1]-=m_d\n",
    "\n",
    "            return True \n",
    "        left = min(stations2)\n",
    "        right = left+k\n",
    "        res = left\n",
    "        while left<=right:\n",
    "            mid = (left+right)//2\n",
    "            if check(mid):\n",
    "                res = mid\n",
    "                left = mid+1\n",
    "            else:\n",
    "                right = mid-1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        n = len(stations)\n",
    "        pre_sum = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            pre_sum[i + 1] = pre_sum[i] + stations[i]\n",
    "        electric_quantity = [0] * n\n",
    "        for i in range(n):\n",
    "            electric_quantity[i] = pre_sum[min(i + r, n - 1) + 1] - pre_sum[max(i - r, 0)]\n",
    "        \n",
    "        def check(min_power: int) -> bool:\n",
    "            diff = [0] * n\n",
    "            diff[0] = electric_quantity[0]\n",
    "            sum_diff = 0\n",
    "            for i in range(1, n):\n",
    "                diff[i] = electric_quantity[i] - electric_quantity[i - 1]\n",
    "            need = 0\n",
    "            for i in range(n):\n",
    "                sum_diff += diff[i]\n",
    "                delta = min_power - sum_diff\n",
    "                if delta > 0:\n",
    "                    need += delta\n",
    "                    if need > k:\n",
    "                        return False\n",
    "                    sum_diff += delta\n",
    "                    if i + 2 * r + 1 <= n - 1:\n",
    "                        diff[i + 2 * r + 1] -= delta\n",
    "            return True\n",
    "\n",
    "        left, right = 0, max(electric_quantity) + k\n",
    "        while left <= right:\n",
    "            mid = left + (right - left) // 2\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        w = -1\n",
    "        sl = []\n",
    "        for i in range(len(stations)):\n",
    "            if w == -1:\n",
    "                left = max ( 0 , i - r)\n",
    "                right = min ( len(stations) - 1, i + r)\n",
    "                w = sum(stations[left : right + 1])\n",
    "            else:\n",
    "                w-= (   0 if i -r -1<0 else stations[i - r -1] )\n",
    "                w+=  ( 0 if i +r  >=len(stations) else stations[i + r ] )\n",
    "            sl.append(w)\n",
    "\n",
    "        if k == 0:\n",
    "            return min(sl)\n",
    "\n",
    "        def dpmin(sl, target):\n",
    "            ans = 0\n",
    "            ad = [ 0 ] * len(sl)\n",
    "            sd = [ 0 ] * len(sl)\n",
    "            for i in range(len(sl)):\n",
    "                val  = ( ad[i-1] if i>=1 else 0 )  -    ( sd[i - 2 * r - 1] if  i>=2 * r else 0 )\n",
    "                sl[i]  += val\n",
    "                ad[i]+=val\n",
    "                if sl[i] < target:\n",
    "                    d = target - sl[i]\n",
    "                    ad[i] += d\n",
    "                    sd[i] = d\n",
    "                    sl[i]+=d\n",
    "                    ans+= d\n",
    "                    if ans > k:\n",
    "                        return False\n",
    "\n",
    "            return ans <= k \n",
    "        minv = min(sl)\n",
    "        l, rr = minv  ,   (minv + k + 2  )   # max(sl) + (k // len(stations) + 2)\n",
    "        mid = (l + rr) // 2\n",
    "        while l <rr :\n",
    "\n",
    "            if dpmin(sl  +  []  , mid) :\n",
    "                if mid == l:\n",
    "                    break\n",
    "                l = mid\n",
    "            else:\n",
    "                rr = mid\n",
    "\n",
    "            mid = (l + rr) //2\n",
    "        return mid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        station_size: int = len(stations)\n",
    "\n",
    "        # get powers by prefix sum\n",
    "        curr_sum = 0\n",
    "        prefix_sum = [0]\n",
    "        for station in stations:\n",
    "            curr_sum += station\n",
    "            prefix_sum.append(curr_sum)\n",
    "        powers = [prefix_sum[min(i + r + 1, station_size)] - prefix_sum[max(i - r, 0)] for i in range(station_size)]\n",
    "        # power_diffs = [powers[0]] + [powers[i] - powers[i - 1] for i in range(1, station_size)]\n",
    "\n",
    "        power_diffs = [0] * station_size\n",
    "        power_diffs[0] = powers[0]\n",
    "        # 求差分数组\n",
    "        for i in range(1, station_size):\n",
    "            power_diffs[i] += powers[i] - powers[i - 1]  # 原始diff\n",
    "\n",
    "        def build_stations(diffs: List[int], loc: int, num: int) -> None:\n",
    "            diffs[loc] += num\n",
    "            if loc + 2 * r + 1 < station_size:\n",
    "                diffs[loc + 2 * r + 1] -= num\n",
    "\n",
    "        def check(x: int) -> bool:\n",
    "            curr_power, count = 0, 0\n",
    "            power_diffs_copy = copy.deepcopy(power_diffs)\n",
    "\n",
    "            for i in range(station_size):\n",
    "                curr_power += power_diffs_copy[i]\n",
    "                if curr_power < x:\n",
    "                    need = x - curr_power\n",
    "                    build_stations(power_diffs_copy, i, need)\n",
    "                    curr_power = x\n",
    "                    count += need\n",
    "                    if count > k:\n",
    "                        return False\n",
    "\n",
    "            return count <= k\n",
    "\n",
    "        left, right = min(powers), max(powers) + k\n",
    "        while left <= right:\n",
    "            middle = (left + right) // 2\n",
    "            if check(middle):\n",
    "                left = middle + 1\n",
    "            else:\n",
    "                right = middle - 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        station_size: int = len(stations)\n",
    "\n",
    "        # get powers by prefix sum\n",
    "        curr_sum = 0\n",
    "        prefix_sum = [0]\n",
    "        for station in stations:\n",
    "            curr_sum += station\n",
    "            prefix_sum.append(curr_sum)\n",
    "        powers = [prefix_sum[min(i + r + 1, station_size)] - prefix_sum[max(i - r, 0)] for i in range(station_size)]\n",
    "        power_diffs = [powers[0]] + [powers[i] - powers[i - 1] for i in range(1, station_size)]\n",
    "\n",
    "        def build_stations(diffs: List[int], loc: int, num: int) -> None:\n",
    "            diffs[loc] += num\n",
    "            if loc + 2 * r + 1 < station_size:\n",
    "                diffs[loc + 2 * r + 1] -= num\n",
    "\n",
    "        def check(x: int) -> bool:\n",
    "            curr_power, count = 0, 0\n",
    "            power_diffs_copy = copy.deepcopy(power_diffs)\n",
    "\n",
    "            for i in range(station_size):\n",
    "                curr_power += power_diffs_copy[i]\n",
    "                if curr_power < x:\n",
    "                    need = x - curr_power\n",
    "                    build_stations(power_diffs_copy, i, need)\n",
    "                    curr_power = x\n",
    "                    count += need\n",
    "                    if count > k:\n",
    "                        return False\n",
    "\n",
    "            return count <= k\n",
    "\n",
    "        left, right = min(powers), max(powers) + k\n",
    "        while left <= right:\n",
    "            middle = (left + right) // 2\n",
    "            if check(middle):\n",
    "                left = middle + 1\n",
    "            else:\n",
    "                right = middle - 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        station_size: int = len(stations)\n",
    "\n",
    "        # get powers by prefix sum\n",
    "        curr_sum = 0\n",
    "        prefix_sum = []\n",
    "        for station in stations:\n",
    "            curr_sum += station\n",
    "            prefix_sum.append(curr_sum)\n",
    "        # windows range: [i - r, i + r]\n",
    "        powers = [prefix_sum[\n",
    "                      min(i + r, station_size - 1)] -\n",
    "                    (0 if (i - r - 1) < 0 else prefix_sum[max(i - r - 1, 0)])\n",
    "                  for i in range(station_size)]\n",
    "\n",
    "        # differences array\n",
    "        power_diffs = [powers[0]] + [powers[i] - powers[i - 1] for i in range(1, station_size)]\n",
    "\n",
    "        def build_stations(diffs: List[int], loc: int, num: int) -> None:\n",
    "            diffs[loc] += num\n",
    "            if loc + 2 * r + 1 < station_size:\n",
    "                diffs[loc + 2 * r + 1] -= num\n",
    "\n",
    "        def check(x: int) -> bool:\n",
    "            curr_power, count = 0, 0\n",
    "            power_diffs_copy = power_diffs[:]\n",
    "\n",
    "            for i in range(station_size):\n",
    "                curr_power += power_diffs_copy[i]\n",
    "                if curr_power < x:\n",
    "                    need = x - curr_power\n",
    "                    build_stations(power_diffs_copy, i, need)\n",
    "                    curr_power = x\n",
    "                    count += need\n",
    "                    if count > k:\n",
    "                        return False\n",
    "\n",
    "            return count <= k\n",
    "\n",
    "        left, right = min(powers), max(powers) + k\n",
    "        while left <= right:\n",
    "            middle = (left + right) // 2\n",
    "            if check(middle):\n",
    "                left = middle + 1\n",
    "            else:\n",
    "                right = middle - 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int: \n",
    "        low = 0\n",
    "        maxr = 2*r+1 \n",
    "        ls = [0] \n",
    "        ls[0] = sum(stations[0:r+1]) \n",
    "        cnt = r + 1 \n",
    "        s = ls[0] \n",
    "        for i in range(1, len(stations)): \n",
    "            if i + r < len(stations): \n",
    "                s += stations[i+r] \n",
    "            cnt += 1 \n",
    "            if cnt > 2*r+1: \n",
    "                s -= stations[i-r-1] \n",
    "                cnt -= 1 \n",
    "            ls.append(s) \n",
    "        up = max(ls) + k\n",
    "        # print(ls) \n",
    "        def check(tg): \n",
    "            d = defaultdict(int) \n",
    "            s = 0 \n",
    "            remain = k \n",
    "            for i in range(len(ls)): \n",
    "                if ls[i] + s >= tg: \n",
    "                    if i - r in d: \n",
    "                        s -= d[i-r] \n",
    "                    continue \n",
    "                diff = tg - ls[i] - s \n",
    "                if remain < diff: \n",
    "                    return False \n",
    "                pos = min(len(ls)-1, i+r) \n",
    "                d[pos] += diff \n",
    "                s += diff \n",
    "                remain -= diff \n",
    "                # if tg == 149: # print(i,d,s,remain) \n",
    "                if i - r in d: \n",
    "                    s -= d[i-r] \n",
    "            return True \n",
    "        \n",
    "        while low <= up: \n",
    "            m = (low+up)//2 \n",
    "            if check(m): \n",
    "                low = m + 1 \n",
    "            else: \n",
    "                up = m - 1 \n",
    "        return low - 1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "\n",
    "        n = len(stations)\n",
    "\n",
    "        diff = [0] * (n + 1)\n",
    "        for i , station in enumerate(stations):\n",
    "            left , right = max(0,i-r) , min(n,i+r+1)\n",
    "            diff[left] += station\n",
    "            diff[right] -= station\n",
    "\n",
    "        def check(target):\n",
    "            cnt = 0\n",
    "            tk = k\n",
    "            d = collections.defaultdict(int)\n",
    "            for i , station in enumerate(diff):\n",
    "                if i == n:continue\n",
    "                cnt += station + d[i]\n",
    "                if cnt < target:\n",
    "                    tk -= target - cnt\n",
    "                    if tk < 0:\n",
    "                        return False\n",
    "                    d[min(n,i+2*r+1)] -= target - cnt\n",
    "                    cnt = target\n",
    "            return True\n",
    "\n",
    "        left , right = min(stations) , sum(stations) + k\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right) >> 1\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        return left if check(left) else left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        N = len(stations)\n",
    "        stationcnt = []\n",
    "        cur = sum(stations[:r])\n",
    "\n",
    "        for mid in range(r+1):\n",
    "            L = mid-r-1\n",
    "            R = mid+r\n",
    "            if R<N:\n",
    "                cur += stations[R]\n",
    "            stationcnt.append(cur)\n",
    "\n",
    "        for mid in range(r+1,N):\n",
    "            L = mid-r-1\n",
    "            R = mid+r\n",
    "            if R<N:\n",
    "                cur += stations[R]\n",
    "            cur -= stations[L]\n",
    "            stationcnt.append(cur)\n",
    "\n",
    "        stationAdd = defaultdict(int)\n",
    "        def getplantcnt(minnums):\n",
    "            curReq = minnums\n",
    "            curSum = 0\n",
    "            R = r\n",
    "            stationAdd.clear()\n",
    "            NR = N-r-1\n",
    "            for mid in stationcnt[:r+1]:\n",
    "                if curReq >= mid:\n",
    "                    diff = curReq - mid\n",
    "                    if R<NR:\n",
    "                        stationAdd[R] += diff\n",
    "                        R+=1\n",
    "                    curReq -= diff\n",
    "                    curSum += diff\n",
    "                    if curSum>k:return 1\n",
    "                else:\n",
    "                    R+=1\n",
    "            L = 0\n",
    "            for mid in stationcnt[r+1: N]:\n",
    "                if L in stationAdd:\n",
    "                    curReq += stationAdd[L]\n",
    "                L+=1\n",
    "                if curReq >= mid:\n",
    "                    diff = curReq - mid\n",
    "                    if R<NR:\n",
    "                        stationAdd[R] += diff\n",
    "                        R+=1\n",
    "                    curReq -= diff\n",
    "                    curSum += diff\n",
    "                    if curSum>k:return 1\n",
    "                else:\n",
    "                    R+=1\n",
    "            return 0\n",
    "        return bisect.bisect(range(k+max(stationcnt)+1), 0, min(stationcnt), key = getplantcnt)-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        station_size: int = len(stations)\n",
    "\n",
    "        # get powers by prefix sum\n",
    "        # curr_sum = 0\n",
    "        # prefix_sum = [0]\n",
    "        # for station in stations:\n",
    "        #     curr_sum += station\n",
    "        #     prefix_sum.append(curr_sum)\n",
    "        prefix_sum = list(accumulate(stations, initial=0))\n",
    "        powers = [prefix_sum[min(i + r + 1, station_size)] - prefix_sum[max(i - r, 0)] for i in range(station_size)]\n",
    "        power_diffs = [powers[0]] + [powers[i] - powers[i - 1] for i in range(1, station_size)]\n",
    "\n",
    "        def build_stations(diffs: List[int], loc: int, num: int) -> None:\n",
    "            diffs[loc] += num\n",
    "            if loc + 2 * r + 1 < station_size:\n",
    "                diffs[loc + 2 * r + 1] -= num\n",
    "\n",
    "        def check(x: int) -> bool:\n",
    "            curr_power, count = 0, 0\n",
    "            power_diffs_copy = copy.deepcopy(power_diffs)\n",
    "\n",
    "            for i in range(station_size):\n",
    "                curr_power += power_diffs_copy[i]\n",
    "                if curr_power < x:\n",
    "                    need = x - curr_power\n",
    "                    build_stations(power_diffs_copy, i, need)\n",
    "                    curr_power = x\n",
    "                    count += need\n",
    "                    if count > k:\n",
    "                        return False\n",
    "\n",
    "            return count <= k\n",
    "\n",
    "        left, right = min(powers), max(powers) + k\n",
    "        while left <= right:\n",
    "            middle = (left + right) // 2\n",
    "            if check(middle):\n",
    "                left = middle + 1\n",
    "            else:\n",
    "                right = middle - 1\n",
    "        return right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxPower(self, stations: List[int], r: int, k: int) -> int:\n",
    "        pre = [0]\n",
    "        for s in stations:\n",
    "            pre.append(pre[-1] + s)\n",
    "            \n",
    "        n = len(stations)\n",
    "        have = [0] * n\n",
    "        for i in range(n):\n",
    "            have[i] = pre[min(n, i + r + 1)] - pre[max(0, i - r)]\n",
    "        # print(have)\n",
    "        i = min(have)\n",
    "        j = max(have) + k\n",
    "\n",
    "        def check(num):\n",
    "            # print(\"k\", k)\n",
    "            # print(\"num\", num)\n",
    "            n = len(have)\n",
    "            diff = [0] * n\n",
    "            delta = 0\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                # print(\"delta\", delta)\n",
    "                # print(\"diff\", diff)\n",
    "                delta += diff[i]\n",
    "                if have[i] + delta >= num:\n",
    "                    continue\n",
    "                cnt += num - have[i] - delta\n",
    "                if i + 2 * r + 1 < n:\n",
    "                    diff[i + 2 * r + 1] -= num - have[i] - delta\n",
    "                delta += num - have[i] - delta\n",
    "                # diff[i] += delta\n",
    "            # print(k)\n",
    "            if cnt <= k:\n",
    "                return True\n",
    "            return False\n",
    "                \n",
    "        while i < j:\n",
    "            mid = (i + j + 1) >> 1\n",
    "            # print(\"mid\", mid)\n",
    "            if check(mid):\n",
    "                i = mid\n",
    "            else:\n",
    "                j = mid - 1\n",
    "                \n",
    "        return i\n",
    "        \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
